Kalman Filter + Applications in Wiimote and Accelerometers

Links :

http://www.gamasutra.com/view/feature/1494/wheres_the_wiimote_using_kalman_.php

[Accelerometer] http://tom.pycke.be/mav/71/kalman-filtering-of-imu-data

Motion Detection in Mobile Games

Motion Detection as Interaction Technique for Games & Applications on Mobile Devices

source: http://www.blogger.com/post-create.g?blogID=6576334769086421977

Here they are discussing a concept of an intuitive interaction technique using optical
inertial tracking on mobile phones.



Optical Motion Detection as Interaction Technology for Mobile Phones

source:http://wiki.forum.nokia.com/index.php/Optical_Motion_Detection_as_Interaction_Technology_for_Mobile_Phones

Mobile phones have small keys and mass market phones are usually equipped with a sub-QVGA-screen. Therefore the possibilities for concepts of interaction with the device are limited to some extent.



Analysis of Built-in Mobile Phone Sensors for Supporting Interactions with the Real World

http://www.medien.ifi.lmu.de/permid2005/pdf/KarinLeichtenstern_Permid2005.pdf

In this paper its investigated that which sensors are already built-in in modern mobile phones and analyze and how they can be employed in real world interactions.

Kalman filter Java code

source: http://mathstat.asu.edu/~eubank/kalman/kalman.html


abstract class kalman{
//members
int t;
matrix Sm1, S, R, HTRinv, M, Sn, A;
vector eps, x, xn, a;

//default constructor
kalman(){}


//Algorithm 4.3
void forward(matrix Sm1m1, vector xm1m1, vector y){
Sm1=F(t-1).times(Sm1m1.times(F(t-1).trans())).plus(Q(t-1));
R=H(t).times(Sm1.times(H(t).trans())).plus(W(t));
HTRinv=R.chol(H(t)).trans();
matrix temp1=Sm1.times(HTRinv.times(H(t)));//temporary storage
S=Sm1.minus(temp1.times(Sm1));
M=F(t).minus(F(t).times(temp1));
vector temp2=F(t-1).times(xm1m1);//temporary storage
eps=y.minus(H(t).times(temp2));
x=Sm1.times(HTRinv.times(eps)).plus(temp2);
}

abstract matrix Q(int i);

abstract matrix F(int i);

abstract matrix H(int i);

abstract matrix W(int i);

//A variant of Algorithm 5.1 that initializes a and A as 0 with updating
//at the beginning of each step rather than the end. Note the ``typo'' in the
//text where M(t-1) is not defined for the last step with t=1. Since a and A
//do not require updating in this case, the algorithm works as written provided
//the last two lines of the for loop are implemented conditionally on t>1.
void smooth(vector aIn, matrix AIn, matrix HTRinvIn, vector epsIn){
a=M.trans().times(HTRinvIn.times(epsIn)).plus(M.trans().times(aIn));
A=M.trans().times(HTRinvIn.times(H(t+1).times(M))).plus(M.trans().times(AIn.times(M)));
xn=x.plus(Sm1.times(a));
Sn=S.minus(Sm1.times(A.times(Sm1)));
}


//access to members

int Gett(){
return t;
}

matrix GetSm1(){
return Sm1;
}

matrix GetS(){
return S;
}

matrix GetR(){
return R;
}

matrix GetHTRinv(){
return HTRinv;
}


matrix GetM(){
return M;
}

matrix GetSn(){
return Sn;
}

matrix GetA(){
return A;
}


vector Getx(){
return x;
}

vector Geteps(){
return eps;
}

vector Getxn(){
return xn;
}

//useful for setting xn=x for last step in forward
//(first step in backward) recursion
void Setxntox(){
this.xn=new vector(x);
}

//useful for setting Sn=S for last step in forward
//(first step in backward) recursion
void SetSntoS(){
this.Sn=new matrix(S);
}



vector Geta(){
return a;
}


//utilities

void printQ(int i){
System.out.println("Q("+i+")");
Q(i).printMatrix();
}

void printF(int i){
System.out.println("F("+i+")");
F(i).printMatrix();
}

void printH(int i){
System.out.println("H("+i+")");
H(i).printMatrix();
}

void printW(int i){
System.out.println("W("+i+")");
W(i).printMatrix();
}

void forwardPrint(){
System.out.println("eps("+t+")");
eps.printVector();

System.out.println("x("+t+"|"+t+")");
x.printVector();

System.out.println("S("+t+"|"+t+")");
S.printMatrix();
}

void backPrint(){
System.out.println("x("+t+"|n)");
xn.printVector();
System.out.println("S("+t+"|n)");
Sn.printMatrix();
}

}

What is Java2 Micro Edition?

Java is known primarily as a server-side programming environment, centered around the technologies that make up the Java 2 Enterprise Edition (J2EE), such as Enterprise JavaBeans (EJBs), servlets, and JavaServer pages (JSPs). Early adopters of Java, however, will recall that it was originally promoted as a client-side application environment. In fact, Java was originally designed as a programming language for consumer appliances. Now Java is returning to its roots with Java 2 Micro Edition, or J2ME for short.

The Java 2 Platform

What we commonly refer to as "Java" is more formally known as the Java 2 Platform. The Java 2 Platform is split into three editions: Java 2 Standard Edition (J2SE), Java 2 Enterprise Edition (J2EE), and Java 2 Micro Edition (J2ME). Each edition of the platform provides a complete environment for running Java-based applications, including the Java virtual machine (VM) and runtime classes.

The three editions all target different kinds of applications running on different kinds of devices. Desktop-based applications are developed using J2SE, which provides the necessary user interface classes. Server-based applications are developed using J2EE, which emphasizes component-based programming and deployment. Handheld and embedded devices are targeted by J2ME.

What separates one edition from another, then, is primarily the set of class libraries that each edition defines. Loosely speaking, you can think of J2ME as a subset of J2SE and J2SE as a subset of J2EE. It is possible to run the same Java bytecode in each edition, providing the classes referred to by the bytecode are available in all three editions. The catch, of course, is that J2ME-based devices have fewer classes than what J2SE and J2EE provide, especially the smaller devices. After all, there are several thousand core J2SE runtime classes, taking up ten to twenty megabytes of space, which is simply too big for the majority of devices out there today and in the near future.

The various specifications that comprise J2ME are all defined through the Java Community Process (JCP), as is done with J2SE and J2EE. Today, there are close to forty separate Java Specification Requests (JSRs) dealing with J2ME: Small device programming is definitely a hot topic within the Java community. (For more information, see the main JCP Web site at www.jcp.org.)

Java 2 Micro Edition

In J2ME, the Java runtime environment is adapted for constrained devices - devices that have limitations on what they can do when compared to standard desktop or server computers. For low-end devices, the constraints are fairly obvious: extremely limited memory, small screen sizes, alternative input methods, and slow processors. High-end devices have few, if any, of these constraints, but they can still benefit from the optimized environments and new programming interfaces that J2ME defines.

Learning about J2ME is not hard: Once you understand the new terminology, it's mostly about learning new APIs (application programming interfaces) and learning how to work in constrained environments. (If you think writing an applet is challenging, wait until you try to fit an application into the 30K of memory some cellphones provide!) You can use most of the same tools you already use in your code development, and with careful coding you can develop libraries of classes that are portable to any device or computer with a Java virtual machine.

PersonalJava and EmbeddedJava

J2ME is not the first attempt at adapting Java for constrained environments. Two other technologies, PersonalJava and EmbeddedJava, made it possible to run Java 1.1.x applications on high-end devices.

PersonalJava uses the basic Java 1.1 runtime classes and throws in a few features from Java 2. Support for some of the runtime classes is optional, but a PersonalJava implementation still requires a couple of of megabytes of memory and a fast processor to run, so it's not a practical solution for truly constrained devices like cellphones and many personal digital assistants.

EmbeddedJava makes every behavior of both the Java VM and the runtime classes optional - the implementor can choose exactly which classes and methods are required. There is one limitation, however: The Java runtime environment can only be used by the implementor and cannot be exposed to third parties. In other words, you can use it to write Java code that runs inside a device, usually as part of the software to control the device, but no one else can write applications for the device. This is done to preserve the "write once, run anywhere" nature of Java, since an EmbeddedJava environment can do away with fundamental things like runtime class verification and change the public interfaces of core classes. EmbeddedJava is really a way to build a "private" Java runtime environment.

Both PersonalJava and EmbeddedJava are being phased out. There is a migration path from PersonalJava to J2ME, as we'll see later in this series, though the current version of PersonalJava continues to be supported. EmbeddedJava is no longer supported because J2ME defines suitable small-footprint runtime environments.

source:http://www.developer.com/ws/j2me/article.php/1378921

Developing Java-Based Mobile Games

For game development GUI development experience with AWT and SWING will be helpful though not mandatory.Browser games are played using mobile phone's built-in microbrowser (net browser for mobile devices), either in online or offline mode. Players can play such games online through their cellular carrier's or a third-party game provider's game Web site, or download them for offline gaming. This category includes a wide range of games, such as solo or multiplayer games, network games, offline games, arcade games, and so forth.

Mobile games can be developed using C++, Java (Java 2 Micro Edition, to be precise), and the Binary Runtime Environment for Wireless (BREW) platform from Qualcomm.

Although C++ has the advantage of being compiled into native code with direct access to system resources, and with BREW the platform provides end-to-end solutions to mobile game developers while allowing them to work with any desired language (including C++, Java, XML, and Flash), Java is the most popular choice for game development. Java, or the Java 2 Micro Edition (J2ME) platform to be precise, is identified as the most convenient for developing mobile games. (For more specifics on J2ME, see "What is Java 2 Micro Edition?") The driving forces behind J2ME's popularity are:

• J2ME enjoys the status of an industry standard backed by all major handset makers, with most of the present day mobile phones being Java-enabled.
• J2ME is a free and open platform. This helps keep the development costs low and provides the necessary flexibility with ample support freely available for developers using it.
• Its highly portable nature ("Write once run anywhere") ensures that a game application written for one brand/type of handset will work with all other brands/types of Java-enabled handsets.
• It is especially optimized for small devices, is lightweight, and is highly secure because applications written on it cannot access or affect other applications running on the phone/device.
• J2ME consists of the Mobile Information Device Profile (MIDP) API that is designed specifically for developing applications for mobile devices including mobile phones, keeping in mind their limitations and constraints. Furthermore, the latest MIDP version 2.0 itself dedicates a whole API to game development, making game development simpler and quicker.

TREMULOUS 1.1.0

Tremulous is a free, open source game that blends a team based FPS with elements of an RTS. Players can choose from 2 unique races, aliens and humans.

Feature List

• Flexible particle system - 99% of the in-game visual effects are configured using particle scripts.
• 16 buildable structures with in-game functions.
• Play as several alien classes with unique abilities.
• Customize your setup as a human and buy new weapons, armour and items.
• Scale the walls and ceilings as an alien waiting for an unsuspecting human.
• Realistic physics and motion - no bunny hopping or quick back peddling.
• Flexible map system - animated mapobjects, triggering, light flares, etc.
• Large weapons system - don't like the weapon you have? Sell it and buy a different one, dozens of options.

Open Source

Tremulous is open source, licensed under the GPL. Tremulous is open source and the source code is available to the public, along with the binaries. It allow other developers to utilise sections of this code in their own works, should it be useful to them. It should be noted however, that using the source makes your work to also be covered by the GPL and hence be open source itself. Tremulous is built on the ioquake3 game engine, which is a development of id software's GPL release of the Quake III Arena source code.

Technical aspects of these games can be discovered by reading the manuals, which can almost always be found in the manual section when we go the the respective site.
e.g:
We can find some technical aspects of how Tremulous works in Section 3 of the manual which can be found in http://tremulous.net/manual/.

Link to download this game:
http://tremulous.net/files/

Comparison of free software shooters

There have been many free software first-person shooters (FPS) projects over the years, from modded Doom and Quake engines to enhance the existing games (ezQuake, EGL, ZDoom), to free art packs such as OpenQuartz or OpenArena. In 2002, along came Cube, a single and multiplayer FPS based on its own engine, including artwork, maps, models and an ingame map editor. In the freeware (and Linux compatible!) world a little-known game called Legends, a Tribes-inspired game, appeared yet remained closed-source. Filling the FPS gap in the open-source world has usually been left up to commercial companies who release their games with Linux support (i.e. Doom3, Unreal Tournament 2004, Loki Software's work) or freeware games produced by commercial studios(i.e. America's Army, Wolfenstein: Enemy Territory) or simply running Windows games run via wine. In the last few years a few built-from-scratch community-based FPS projects, most built on the GPLed Quake engines, have popped up, among them are Tremulous, Alien Arena, Nexuiz, and War§ow. Some have kept their art assets under a closed license (War§ow), while others have also released their art under an OSS license (Nexuiz).
For this comparison, we'll take a look at active, robust and community-developed free software shooters. Most released free software shooters are designed for multiplayer, a logical step for a game developed in an online community, however most also feature a bot-based single-player mode.This feature seeks to be a little more thorough and go a step further, ranking the following seven games: Alien Arena, Nexuiz, OpenArena, Sauerbraten, Tremulous, War§ow, and World of Padman. In ranking these games, gameplay, design, innovation and presentation (in that order) will be held as primary criteria.

1. War§ow

War§ow is a deathmatch shooter with a focus on freedom of movement, attracting new players and fostering a competitive scene. It is built on Qfusion, a heavy modification of the GPL Quake 2 engine. From the user interface, to the gameplay, to even the netcode the game feels more like an improvement on Quake 3 than anything, stretching far beyond the original Quake 2 engine. Along with World of Padman, wSw stands out in this comparison by actually using colorful and clean graphics as opposed to Quake-inspired dark visuals. Warsow manages set itself even further by using cel-shading to create very clean, yet stunning visuals which regrettably can strain slower systems. In addition, the maps all feature a unique visual style that varies between maps yet retains the clean and cyberpunk visual themes.While sticking to basic deathmatch gamemodes, wSw manages to refine them and remain fun and enjoyable. Weapons are generally the same as Quake 3 and 4, although with a more polished feel. wSw however, implements a dual tier system for ammos. Weapons have weak and strong ammos which add more functionality to the gameplay while still keeping the basics simple. War§ow’s main change on top of basic Quake 3 gameplay is an expansion of movement options, featuring strafejumping and bunnyhopping from Quake along with dash, walljumping and aircontrol. Polish and high quality standards are what make War§ow the free software FPS to beat. All aspects, from movement to maps to the gamemodes, seem refined and balanced. It was not until the mid-2007 release of the 0.3x version (currently 0.32) that wSw became refined enough to set itself apart from the others mentioned here. While many of the previously mentioned games have good original ideas and interesting features, they do not present games that match the quality of commercial offerings. In terms of multiplayer features and customizability, War§ow matches and outclasses any released commercial deathmatch game. Many of the other games seem to fall into the common trend in free software projects: lots of great ideas without friendly and useful implementation, while War§ow is in the style of Firefox, polished and accessible. Maps seem to have serious consideration for item placement and flow, voice-overs seem clean and crisp, lag-compensating network code keeps online play smooth. While many games seem to concentrate in only one area, Warsow seems to do well in almost every area. teamplay, 1v1, new players and experienced players all have been considered in design. Out of the previously mentioned games War§ow also has the largest community with over 250 servers. Competitive gaming is a key part of wSw and there exists a very large competitive community, for example, an international LAN competition was hosted in 2007. Competition drives many of the design decisions behind the game, and always leaves players with something to do and strive for. This also leads to the game's largest flaw, a steep learning curve that pushes wSw beyond the scope of many casual gamers; although the newly added Clan Arena mode lets new players have a simple gamemode where they can stand a bit more of a chance. wSw thrives on bunnyhopping and strafing skills which take time to develop, tutorial videos exist but lack of an ingame tutorial seriously limits adoption. The high quality art direction, the implementation of some simple yet effective original ideas, combined with the refined Quake gameplay leaves War§ow the champion of the pack for free software shooters. Warsow was able to do what many free software projects strive for, take an established concept, clearly implement additional original ideas, refine the core of the project, and then present it in a very professional way.

2. Tremulous

Tremulous sets itself aside from all of the previous games in that it isn’t a FFA deathmatch game. Instead Tremulous is a team-based game with aliens vs. humans where each team constructs a base and players are given the ability to obtain individual upgrades. With a kill-based point system, Tremulous rewards combat, allowing players to get better equipment so they can better attack the opponents. The two teams are unique and the concept and style of the game is rather original. If anything, Tremulous can be related to the Half-Life mod Natural Selection, although without the RTS commander mode. Tremulous has had a very constant release cycle with the latest 1.1 being released about a year ago and the community and development remaining active. The game is based on the Quake 3 engine, and although there are only 8 maps, they’re all varied, unique and high-quality. The only notable flaw was that the options menu didn’t show up until the player joined a game. Tremulous has rich gameplay but still very accessible to new players, featuring onscreen help and tips while you play. To further the point, Tremulous comes with a descriptive and friendly manual for those who want to learn the details of the gameplay. The game is simply fun; there is just action for those who want a simple game and tons of features and detail for those that want a bit more. The graphic design is consistent, dark and sci-fi futuristic with a bit of variance but a lot of consistency. The game has a large following as far as free software goes with a about 200 servers and at least a couple games any time of day. The performance is clean and consistent and it looks as good as Quake 3 generation mods. Tremulous is one of the few free software projects to combine an original idea with a polished implementation and good direction. The few maps and one gamemode really keep the style focused and clean. Tremulous could use more maps, more variety, more content and perhaps more robust gameplay, but 1.1 is a great release and future versions are definitely something to watch out for.



3. World of Padman

World of Padman originated as a modification on top of Quake 3 in 2004. With the release of GPL licensed Quake3 code, World of Padman was released as a stand-alone game on top of ioquake3. From that perspective, World of Padman was designed more in the style of the mod community (art-driven projects) than that of the free software community (code-driven projects) but nonetheless, its free software now. The game is based on a comic book and has unique colorful graphics with clear comic inspiration. World of Padman gameplay is very similar to that of Quake3, a little bit different, a little refreshing, but nothing too strikingly new. Killing other players is satisfying and just silly fun. If anything, World of Padman is proof that deathmatch gaming doesn’t need to be blood-covered, violent and serious; it can be silly, cutesy and fun. World of Padman features several maps, each quite unique and but fitting with a common style. For example, players are characters about 3cm high and fight in real rooms like a bedroom, library, kitchen, etc. It’s not a new approach for maps, but it definitely is fun and interesting; combined with World of Padman’s art direction, this leaves for rather refreshing arenas. And while maps like this sure are great free-for-all fun, they aren’t really designed for competitive play, limiting potential for a hardcore community (the driving force of many shooter games). Gameplay is similar to Quake3 with slower rockets and a very satisfying machine gun being the most notable differences. It has a small community at about 26 servers but the large installer above 500MB might be slowing adoption. The game is very polished , it has several gamemodes (including a unique “Spray your Color” mode) but gameplay still boils down the basic Quake-like fragging. While World of Padman is not, by any stretch of the imagination, a bad game, it lacks the innovative gameplay design goals of several of the games features here, it feels like Quake with polish and restructured objectives. While the game has great style rivaling the stylistic nature of any commercial game, it lacks advanced graphical features of Nexuiz & Sauerbraten or unique gameplay features of Nexuiz & Alien Arena. If you want to see what the gothic Quake 3 would look like if it were designed by color-loving comic artists with a sense of humor and a sense of fun style, World of Padman is exactly what you’re looking for but regrettably that’s about as far is it goes at the moment.

4. Nexuiz

Nexuiz is another game that follows the fast, dark, and intense free-for-all deathmatch style first set down by Quake 1 in 1996. Nexuiz curiously enough is built on the Darkplaces engine, an expanded version of the GPL released Quake 1 source. While the basic graphics are seem to be up to Quake 3 standards, expanded lighting options allow the graphical features to be brought up to just below Quake 4 standards. Although the newest version still follows that simple deathmatch style, the fast, varied maps and lots of explosive action with interesting two fire-mode weapons leads to gameplay that is about as intense as it gets for shooters. Good sound combined with varied and unique weapons attests to the polish that has gone into bringing Nexuiz up to version 2.3. Nexuiz has lots of maps which seem to be slightly varied in style, but still are predominantly covered with dark overtones. While most of the game is cleaned up far beyond its Quake 1 roots, it is still lacking in presentation with the menu being very circa 1990s. The community is strong and with about 80 servers, and finding a game is fairly easy. Nexuiz has lots of content, style and features and is very well done for a FFA game but some areas could use some more work and showcasing of its unique features and modes.

5. Alien Arena

Alien Arena is a Quake 2 based deathmatch game that tries to draw on a conflict between humans and aliens. However this distinction between two player types rarely stretches beyond player models. The latest release, Alien Arena 2007 6.10, still has many visual characteristics that appear outdated and reminiscent of Quake 2. Although there are game modes such as deathball, CTF, and assult, with a dark artistic style, fast gameplay with strong weapons, Alien Arena is predominantly a deathmatch game. The original game modes aren’t very well presented and seem to be underutilized, which is a shame because they seem to be fairly innovative. For example, Alien Arena includes vehicles in certain game modes, but the feature is hidden away on a few rarely-played and rarely-promoted maps. Although the external server browser and main menu are very nice, much of Alien Arena seems to be muddled and lacking polished design. The HUD lacks many critical features like a weaponlist or a clock, and the icons and graphics are not clear. Alien Arena lacks many obvious gameplay features that have become standard in modern games, like removing the quad powerup for the duel gamemode. While many of the weapons seem to be recreations of weapons in Unreal and Quake, the two fire modes for each weapon adds interesting diversity on top of Quake-inspired gameplay rules. But overpowered nature of the weapons, especially the chaingun, leaves much to be desired from the gameplay. The community isn’t very large at about 60 servers, but the game seems to be a bit lacking in clean presentation so it may not be as attractive to new players. Alien Arena seems to be working with lots of new and interesting original concepts but still needs work to match the artistic and gameplay quality of the other games covered here. If the project were to shift gears and focus a bit more on polish, design and presentation instead of creating tons of content (which it already has lots of), it has the potential to move beyond "dark FFA deathmatch action" and really be something quite original and remarkable.

6. OpenArena

OpenArena is a project to create GPL-licensed art assets on top of the open-sourced Quake 3 engine. It uses the latest snapshot of the ioquake3 engine and a mix of GPL assets ranging from original work to resources from Nexuiz, Cube and others. OpenArena 0.71 is a fairly large release at over 200MB. Most of the space is spent on many maps and models, some of which are regrettably lacking in quality. Some are straight recompiles of the GPL released Quake 1 maps (oa_dm1-7), which fail to use many of the advanced lighting and detail offered in the new engine. OpenArena seems to generally lack coherent art direction or design; most the maps, models and artwork seems like a half-done mix of Quake 3’s gothic architecture and anime. The gameplay stays true to what was included in Quake3, so it can be rather enjoyable. On the other hand, much of Quake 3 Arena's popularity came from being done in such a simple, directed, and polished manner and OpenArena lacks much of the polish that made Quake3 so enjoyable. However, the project is still in its early stages and the task at hand is a rather large one. The goal of recreating GPL Q3A artwork on top of the GPL code is both noble and a great contribution to the community. OpenArena games still seem limited to FFA and with about 70 servers, the community is rather small. While Q3A gained popularity as a competitive game, the developers of OA don’t see that as a target market so the depth of gameplay is unlikely to expand. At the moment, most the games on this list display far better art direction and design, which is regrettable as OpenArena is the most art-driven and least code-driven game in the group. At the end of the day though, OpenArena is about making a free game that has lots of simple & fun deathmatch action a la Quake3, and that is where it succeeds.

7. Sauerbraten

Sauerbraten is basically Cube 2, the sequel to one of the most influential free software shooters released to date. The engine is completely reworked with brand new graphics rendering features rivaling that of Quake4. Like Cube, Sauerbraten has a built-in map editor that allows player to edit maps from within the game, making this one of the friendliest games for content-creation. The latest version of Sauerbraten, 2007-09-04, is little more than a subversion snapshot packaged and stabilized for wider distribution; the game is still in heavy development. Sauerbraten gameplay drastically differ from anything Cube offered, with simple Quake-style weapons, game effects, and the same Quake3-like FFA action. It is worth noting that Cube (and Sauerbraten) give you a weapon when you pick up the appropriate ammobox; there is no separation between ammo and weapons.While it has some cool features, the game still feels like more of a concept demo than an actual game, and with only 20-30 servers, half running instagib, there isn’t much of a community following. Single player is reminiscent of Quake1, with enemy monsters in a variety of maps. The menu is actually one of the coolest I’ve seen implemented in a game, it spawns as an object ingame and faces you, however the lack of a main menu upon load adds to the tech-demo feel. Despite the tech-demo nature of the game, Sauerbraten has a good soundtrack, lots of maps, good quality models, well-done artwork and textures. The gameplay isn’t anything astounding but with pretty decent maps and gameplay reminiscent of Quake3, Sauerbraten definitely offers something for people who just want some simple mindless action with some eye candy. Sauerbraten is a really cool project, but right now it remains that, a project of what can be done, more than a game.

source:
http://www.linux-gamers.net/smartsection.item.81/comparison-of-free-softwareshooters.html

"Shut Not Your Doors

Shut not your doors to me proud libraries,
For that which was lacking on all your well-fill'd shelves, yet
needed most, I bring,
Forth from the war emerging, a book I have made,
The words of my book nothing, the drift of it every thing,
A book separate, not link'd with the rest nor felt by the intellect,
But you ye untold latencies will thrill to every page."

LEAVES OF GRASS By Walt Whitman :)

A Quick Insight

It's not a filter at all, it's a recursive estimator which is very convenient to implement as a computer algorithm ; i.e. for each instance, you use the previous output as an input.

To grasp the meaning of Kalman Filter by starting from definitions and complicated equations is nearly impossible.The equation below, is much easier to start with.

The k's on the subscript are states. Here we can treat it as discrete time intervals, such as k=1 means 1ms, k=2 means 2ms.

Our purpose is to find , the estimate of the signal x. And we wish to find it for each consequent k's.

Also here, is the measurement value. Keep in mind that, we are not perfectly sure of these values. Otherwise, we won't be needing to do all these. And is called "Kalman Gain" (which is the key point of all these), and is the estimate of the signal on the previous state.

The only unknown component in this equation is the Kalman Gain . Because, we have the measurement values, and we already have the previous estimated signal. You should calculate this Kalman Gain for each consequent state.

On the other hand, let's assume to be 0.5, what do we get? It's a simple averaging! In other words, we should find smarter coefficients at each state. The bottom line is :

"Kalman filter finds the most optimum averaging factor for each consequent state;& somehow remembers a little bit about the past states."

Build a Model

First of all, we must be sure that, Kalman filtering conditions fit to our problem.

The two equations of KLF are:

It means that each x_k (our signal values) may be evaluated by using a linear stochastic equation (the first one). Any x_k is a linear combination of its previous value plus a control signal u_k and a process noise (which may be hard to conceptualize). Remember that, most of the time, there's no control signal u_k.

The second equation tells that any measurement value (which we are not sure its accuracy) is a linear combination of the signal value and the measurement noise. They are both considered to be Gaussian.

The process noise and measurement noise are *statisticlly independent. [*(of events or values) having the probability of their joint occurrence equal to the product of their individual probabilities.] The entities A, B and H are in general form matrices. But in most of our signal processing problems, we use models such that these entities are just numeric values. Also as an additional ease, while these values may change between states, most of the time, we can assume that they're constant. If we are pretty sure that our system fits into this model , the only thing left is to estimate the mean and standard deviation of the noise functions Wk-1 and vk. We know that, in real life, no signal is pure Gaussian, but we may assume it with some approximation. This is not a big problem, because we'll see that the Kalman Filtering Algorithm tries to converge into correct estimations, even if the Gaussian noise parameters are poorly estimated. The only thing to keep in mind is : "The better you estimate the noise parameters, the better estimates you get."

Starting the Process

When you fit your problem(model) into the KLF, the next step is to determine the parameters and the initial values.

We have two distinct set of equations :

*Time Update (prediction) and *Measurement Update (correction). Both equation sets are applied at each k^th state.

[*Can be derived from the linear stochastic difference equation (2 equations of KLF), by taking the partial derivative and setting them to zero ]

Time Update (prediction)

Measurement Update (correction)

When we make the modeling , we know the matrices A, B and H. Most probably, they will be numerical constants.(And even most probably, they'll be equal to 1.)

R is rather simple to find out, because, in general, we're quite sure about the noise in the environment. But finding out Q is not so obvious.

To start the process, we need to know the estimate of x₀, and P₀.

Iterate

Since we gathered all the information we need and started the process, now we can iterate through the estimates. Previous estimates will be the input for the current state.

Here, is the "prior estimate" which in a way, means the rough estimate before the measurement update correction. And also is the "prior error covariance". We use these "prior" values in our Measurement Update equations. In Measurement Update equations, we really find which is the estimate of x at time k (the very thing we wish to find). Also, we find which is necessary for the k 1 (future) estimate, together with . The Kalman Gain ( ) we evaluate is not needed for the next iteration step, it's a hidden, mysterious and the most important part of this set of equations. The values we evaluate at Measurement Update stage are also called "posterior" values. Which also makes sense.

source: http://bilgin.esme.org

********************************************************

A Simple Example

Now let's try to estimate a scalar random constant, such as a "voltage reading" from a source. So let's assume that it has a constant value of aV (volts) , but of of course these are noisy readings above and below a volts. And we assume that the standard deviation of the measurement noise is 0.1 V.

Now let's build our model:

We have reduced the equations to a very simple form.

• Above all, we have a 1 dimensional signal problem, so every entity in our model is a numerical value, not a matrix.

• We have no such control signal u_k, and it's out of the game

• As the signal is a constant value, the constant A is just 1, because we already know that the next value will be same as the previous one. We are lucky that we have a constant value in this example, but even if it were any other linear nature, again we could easily assume that the value A will be 1.

• The value H = 1, because we know that the measurement is composed of the state value and some noise. You'll rarely encounter real life cases that H is different from 1.

Let's as

TIME (ms)	1	2	3	4	5	6	7	8	9	10
VALUE (V)	0.39	0.50	0.48	0.29	0.25	0.32	0.34	0.48	0.41	0.45

We should start from somewhere, such as k=0. We should find or assume some initial state. Here, we throw out some initial values. Let's assume estimate of X₀ = 0, and P₀ = 1. Then why didn't we choose P₀ = 0 for example? It's simple. If we chose that way, this would mean that there's no noise in the environment, and this assumption would lead all the consequent to be zero (remaining as the initial state). So we choose P₀ something other that zero.

Let's write the Time Update and Measurement Update equations.



Now, let's calculate the values for each iteration.

Here, I displayed the first 2 state iterations in detail, the others follow the same pattern. I've completed the other numerical values via a computer algorithm, which is the appropriate solution.

The chart here (right) shows that the Kalman Filter algorithm converges to the true voltage value. Here, I displayed the first 10 iterations and we clearly see the signs of convergence. In 50 or so iterations, it'll converge even better.

To enable the convergence in fewer steps, you should

• Model the system more elegantly
• Estimate the noise more precisely

Applications of KLF (Research Papers)

1.An Extended Kalman Filtering Approach to Modeling Nonlinear Dynamic Gene Regulatory Networks via Short Gene Expression Time Series

In this paper, the extended Kalman filter (EKF) algorithm is applied to model the gene regulatory network from gene time series data. The gene regulatory network is considered as a nonlinear dynamic stochastic model that consists of the gene measurement equation and the gene regulation equation. After specifying the model structure, the EKF algorithm is applied for identifying both the model parameters and the actual value of gene expression levels. It is shown that the EKF algorithm is an online estimation algorithm that can identify a large number of parameters (including parameters of nonlinear functions) through iterative procedure by using a small number of observations. Four real-world gene expression data sets are employed to demonstrate the effectiveness of the EKF algorithm, and the obtained models are evaluated from the viewpoint of bioinformatics.

2.Relaxed parametric design with probabilistic constraints

Parametric design is an important modelling paradigm in computer-aided design. Relationships (constraints) are specified between the degrees of freedom (DOFs) of the model, instead of the DOFs themselves, resulting in efficient design modifications and variations. Current parametric modellers require an exact specification of all the constraints involved, which causes overwork for the designer during design iterations. The relaxed-parametric-design modelling paradigm is described, in which decisions which needlessly limit the freedom of design in later stages are avoided. The designer usesb soft constraints, and specifies the level of exactness with which they are to be met. As a specific scheme for implementing relaxed parametric design, probabilistic constraints are presented, where a parametric model is viewed as a stochastic process. The softness of a constraint is represented as the covariance of a suitably distributed random variable. A novel method is described of expressing the DOFs and the model as a system of probabilistic equations, which is then solved using the Kalman filter, a powerful estimation tool for stochastic systems. An a priori covariance matrix associated with a DOF can be used as a guideline for the solver to select a particular solution from multiple solutions.

3.An alternative Kalman innovation filter approach for receiver position estimation based on GPS measurements

This article presents an alternative Kalman innovation filter approach for receiver position estimation, based on pseudorange measurements of the global positioning system. First, a dynamic pseudorange model is represented as an ARMAX model and a pseudorange state-space innovation model suitable for both parameter identification and state estimation. The Kalman gain in the pseudorange coordinates is directly calculated from the identified parameters without prior knowledge of the noise properties and the receiver parameters. Then, the pseudorange state-space innovation model is transformed into the receiver state-space innovation model for optimal estimation of the receiver position. Hence, the proposed approach overcomes the drawbacks of the classical Kalman filter approach since it does not require prior knowledge of the noise properties, and the receiver's dynamic model to calculate the Kalman gain. In addition, due to its simplicity, it can be easily implemented in any receiver. To demonstrate the effectiveness of the approach, it is utilized to estimate the position of a stationary receiver and its performance is compared against two versions of the classical Kalman filter approach. The results show that the proposed approach yields consistently good estimation of the receiver position and outperforms the other methods.

4 Parallel computation of the modified extended kalman filter

In this paper, certain techniques for mapping the modified extended Kalman filter (MEKF) onto systolic array processors are described. First, a square-root algorithm based on the singular value decomposition (SVD) for the Kalman filteris introduced. Then, VLSI architecture of the systolic array type for its implementation is developed. Compared with other existing square-root Kalman filtering algorithms, this new design is numerically more stable and has nicer parallel and pipelining characteristics when it is applied to the MEKF. Moreover, it achieves higher efficiency. For n-dimensional state vector estimations, the proposed architecture consists of O(3/2n²) processing elements and completes an iteration in time O((s + 8)n), in contrast to the time complexity of O((s + 3)n³) for a sequential implementation, where s ≈ log n.

When you are at a cross road...

To see a world in a grain of sand
Or a heaven in a wild flower,
Hold infinity in the palm of your hand
And eternity in an hour.
WILLIAM BLAKE (1757-1827)

Some good links about research : Thanks to (http://damithakumarage.wordpress.com/)

[1] http://www.cse.iitk.ac.in/users/jalote/GenArticles/ET23-06-03.htm
[2] http://www-2.cs.cmu.edu/~mblum/research/pdf/grad.html
[3] http://www-2.cs.cmu.edu/~harchol/gradschooltalk.pdf

Target Tracking Using (EKF)


sources:
1- http://www.engineeringletters.com/issues_v14/issue_1/EL_14_1_27.pdf
2- ieeexplore.ieee.org/iel2/382/4762/00186519.pdf
3-http://doi.ieeecomputersociety.org/10.1109/ISISE.2008.286

Simultaneous localization and mapping (SLAM)

sources:

1-http://www.doc.ic.ac.uk/~ajd/Robotics/RoboticsResources/SLAMTutorial1.pdf
2-http://www.doc.ic.ac.uk/~ajd/Robotics/RoboticsResources/SLAMTutorial2.pdf
3-http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping


SLAM is a technique used by robots and autonomous vehicles to build up a map within an unknown environment (without a priori knowledge) or to update a map within a known environment (with a priori knowledge from a given map) while at the same time keeping track of their current location.
Mapping is the problem of integrating the information gathered for and /or with an autonomous entity (the robot's) sensors into a complex model and depicting with a given representation.
by the first characteristic question What does the world look like? Central aspects in mapping are the representation of the environment and the interpretation of sensor data.

• Mapping
• Sensing
• Locating
• Modeling

The lesser the precision of any locating process might result, the more the support of a locally relevant map improves the assessing of the real location. However, maps generally represent the status at the time of drawing the map, not necessarily consistent with the actual status of the environment at the time of using the map.
Complexity of the technical processes of locating and mapping under conditions of errors and of noise do not allow for a coherent solution of both tasks. Simultaneous localization and mapping (SLAM) is a concept to bind these processes in a loop and therefore supports the contiguity of both aspects in separated processes. Iterative feedback from one process to the other one enhances the results of both consecutive steps.localization is the problem of estimating the place (and pose) of the robot relative to a map. In other words, the robot has to answer the second characteristic question, Where am I? Typically, solutions comprise tracking, where the initial place of the robot is known, and global localization, in which no or just some a priori knowledge about the ambience of the starting position is given.

SLAM is therefore defined as the problem of building a model leading to a new map or repetitively improving an existing map while at the same time localizing the robot within that map.

To find what the environment looks like given a set of observations, a robot needs to know the robot's own kinematicswhich qualities the autonomous acquisition of information has, from which sources additional supporting observations have been made.

Extended Kalman Filter (EKF)

sources:
1-http://users.isr.ist.utl.pt/~mir/pub/kalman.pdf
2-http://en.wikipedia.org/wiki/Extended_Kalman_filter

The Kalman filter dynamics results from the consecutive cycles of prediction
and filtering. The dynamics of these cycles is derived and interpreted in the framework
of Gaussian probability density functions. Under additional conditions on
the system dynamics, the Kalman filter dynamics converges to a steady-state filter
and the steady-state gain is derived.
The nonlinear version of the Kalman filter which linearizes about the current mean and covariance is the Extended Kalman Filter.With no loss of generality we will consider that
the system has no external inputs.


One iteration of the EKF is composed by the following consecutive steps:

1. Consider the last filtered state estimate ˆx(k|k),
2. Linearize the system dynamics, xk+1 = f(xk) + wk around ˆx(k|k),
3. Apply the prediction step of the Kalman filter to the linearized system dynamics
just obtained, yielding ˆx(k + 1|k) and P(k + 1|k),
4. Linearize the observation dynamics, yk = h(xk) + vk around ˆx(k + 1|k),
5. Apply the filtering or update cycle of the Kalman filter to the linearized
observation dynamics, yielding ˆx(k + 1|k + 1) and P(k + 1|k + 1).

Let F(k) and H(k) be the Jacobian matrices of f(.) and h(.), denoted by
F(k) = 5fk |ˆx(k|k)
H(k + 1) = 5h |ˆx(k+1|k)

The Extended Kalman filter algorithm is stated below:

Predict Cycle

ˆx(k + 1|k) = fk(ˆx(k|k))
P(k + 1|k) = F(k)P(k|k)FT (k) + Q(k)

Filtered Cycle
//not formatted
x(k + 1|k + 1) = ˆx(k + 1|k) + K(k + 1)[yk+1 − hk+1(ˆx(k + 1|k))]
K(k + 1) = P(k + 1|k)HT (k + 1)[H(k + 1)P(k + 1|k)HT (k + 1) + R(k + 1)]−1
P(k + 1|k + 1) = [I − K(k + 1)H(k + 1)]P(k + 1|k)

It this important to state that the EKF is not an optimal filter, but rathar it is
implemented based on a set of approximations. Thus, the matrices P(k|k) and
P(k + 1|k) do not represent the true covariance of the state estimates.
Moreover, as the matrices F(k) and H(k) depend on previous state estimates
and therefore on measurements, the filter gain K(k) and the matrices P(k|k) and
P(k + 1|k) cannot be computed off-line as occurs in the Kalman filter.
Contrary to the Kalman filter, the EKF may diverge, if the consecutive linearizations
are not a good approximation of the linear model in all the associated
uncertainty domain. [1]