## Tuesday, March 8, 2011

### How to Keep Numerous Tabs Open in Google Chrome

I try not to open too many tabs in Google Chrome, however, it still happens. When many tabs are open it slows down the system and take up a lot memory. An easy work around to this is to end all tabs that are not currently in use. To do this simply press Shift+Escape to bring up Chrome's task manager. End all tabs that are not being used or are taking a large share of the memory. The tab remembers its URL but doesn't load anything into memory. Refresh the page to load the contents again. Now one can have as many tabs open without slowing the system.

## Friday, February 11, 2011

### String Literals

What is wrong with the following code?

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
char *str = "hello world";

str[0] = 'H';

return 0;
}

## Saturday, February 5, 2011

### XOR Swap Algorithm

XOR swap algorithm is a nifty little trick to swap two variables with each other without a temporary variable.

Here is a little snippet of code showing how it works:
 #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char **argv) { int x, y; x = 123; y = 456; cout << "x = " << x << endl; // x = 123 cout << "y = " << y << endl; // y = 456 cout << endl; // Swap values x ^= y; y ^= x; x ^= y; cout << "x = " << x << endl; // x = 456 cout << "y = " << y << endl; // y = 123 return 0; } 

### Reverse Words in a String

Reverse the order of words in a string "jackdaws love my big sphinx of quartz" to "quartz of sphinx big my love jackdaws"

Solution 1: Using a Stack
Assumption: The string literal is given in a String
 public String reverseString(String myStr) { String [] myStrSplit = myStr.split("-"); Stack<String> stack = new Stack<String>(); StringBuilder myStrReverse = new StringBuilder(); for ( String s : myStrSplit ) { stack.push( s ); } while ( !stack.empty() ) { myStrReverse.append( stack.pop() ); } return myStrReverse.toString(); } 

Time Complexity
String#split + pushing on stack + popping off stack
N + N + N time
= O( 3N )

Space Complexity
myStr + myStrSplit + stack + myStrReverse
N + N + N + N
= O( 4N )

Solution 2: Using a Doubly LinkedList
 public void reverseString(DLinkedList myStr) { Node next, prev; for ( Node n : myStr ) { next = n.next; prev = n.prev; n.next = prev; n.prev = next; } }

Time Complexity
traverse myStr
= O( N )

Space Complexity
Space for next and prev
= O( 1 ) (constant space)

Solution 3: Using XOR

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

// Find next space position
inline int nextSpacePosition(char *str, int startPosition)
{
int nextSpacePosition = -1;

for ( int i = startPosition; str[i] != '\0'; ++i )
{
if ( str[i] == ' ' )
{
nextSpacePosition = i;
break;
}
}

return nextSpacePosition;
}

// XOR Swap
inline void swap(char *a, char *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

int main(int argc, char **argv)
{
char *originalStr = "jackdaws love my big sphinx of quartz";
char reverseStr[256];
int strLength;
int pos, spacePos;
bool lastIteration = false;

pos = 0;
spacePos = 0;
strcpy(reverseStr, originalStr);
strLength = strlen(reverseStr);

// Reverses string
for ( int i = 0; i < strLength/2; ++i )
{
swap(reverseStr[i], reverseStr[strLength-i-1]);
}

// Reverses words
while ( ! lastIteration )
{
// Find where word ends (space)
spacePos = nextSpacePosition( reverseStr, spacePos+1 );

if ( spacePos == -1 )
{
spacePos = strLength;
lastIteration = true;
}

// Reverse word
int end = pos + ((spacePos-pos) / 2);
for ( int i = pos; i < end; ++i )
{
swap( reverseStr[i], reverseStr[spacePos-1-(i-pos)] );
}

pos = spacePos + 1;
}

cout << "Original: " << originalStr << endl;
cout << "Reversed: " << reverseStr << endl;
}

Time Complexity
traverse half of reverseStr (reversing the string) + traverse reverseStr (reversing words) + string length
= O( 5/2 * N )
= O( N )

Space Complexity
Space for constant space variables
= O( 1 ) (constant space)

The appealing feature for this method is that it doesn't require any "new" data structures (i.e., linked list) and all the work is done in place.

## Tuesday, October 19, 2010

### Testing a Device

An interesting question is how do you test a device (e.g., vending machine, toaster, pencil, magical food creator appliance). There is no correct answer to this question but a correct thought processLike any problem that we face as an scientist/engineer is to start from the top. It is very important at this point to understand the big picture.

For a tester this means, what are the requirements of the device? A requirements document is what the product should be or perform. The requirements define the design of the product. There is also specifications which are derived from the requirements. The developer and tester shouldn't worry about writing the specifications, just that they are met, and that they have good requirements.

FURPS represent a good model for classifying software quality attributes. Use FURPS as a high level mental checklist. From there, you can branch into each category and drill down with specific tests.

Functionality - Feature set, Capabilities, Generality, Security
Usability - Human factors, Aesthetics, Consistency, Documentation
Reliability - Frequency/severity of failure, Recoverability, Predictability, Accuracy, Mean time to failure
Performance - Speed, Efficiency, Resource consumption, Throughput, Response time
Supportability - Testability, Extensibility, Adaptability, Maintainability, Compatibility, Configurability, Serviceability, Installability, Localizability, Portability

Other things to keep in mind: input/output, display, and data model.

Related articles:

## Sunday, April 25, 2010

### Model Reconstruction from Images

In the coming days I will talk about model reconstruction from images. I have developed a very simple framework for doing reconstruction. The framework consists of feature detection, correspondences, removing of incorrect data, distortion removal, computing the projection matrices, triangulation, and mesh creation. The discussion will involve a simplified problem space. Proofs for methods are left out of the explanation as the project’s scope is to perform the operations rather than the theory that goes behind it.

The rig consists of a free moving calibrated camera at a single focus.

Image Capture

 Images taken with web cam
First step is to capture images. The camera must have the same focus for all images, including the images used for camera calibration. For simplicity, the Microsoft LifeCam NX-6000 web cam was used as it has a single focal length. A regular compact camera would give the best results. Compact cameras have a better image sensor (CCD) and lenses rather lower quality image sensor (CMOS) and lenses found in web cams.

Feature Detection

A good feature detector is to create a consistent feature point amongst different images. Characteristics of a good detector are invariant to changes to scale, noise, illumination, and affine (scale and translation) transform. Feature point detection is primarily done with the algorithm called Scale Invariant Feature Transform, or SIFT. Rather than re-implementing available solutions, the project used the VLFeat library. SIFT is invariant to scale, orientation, affine distortion, partially invariant to illumination changes [ref].

Correspondences
 Correspondences between two images, 220 points
The VLFeat library also does image correspondences. An advantage of SIFT is that its feature points have an associated vector to them. To compare two features to each other one only has to look at the Euclidean distance between the two vectors. However, this is all taken care by the library.

Although SIFT is a fairly accurate algorithm, it isn’t perfect. Poor quality features can occur in parts of the image that the color data rapidly changes (i.e., a tree’s leaves), parts were color data doesn’t change (i.e., a flat solid area), highly saturated or under-saturated areas (i.e., lights, darkness), or highly specular or reflective surfaces (i.e. chrome, mirrors). Additionally, there can be bad correspondences from mismatching feature points.

Removing Incorrect Correspondences
 Image correspondences after RANSAC, 84 points
Random Sample Consensus, or RANSAC, was used to remove bad data. RANSAC is an iterative method to estimate parameters of the mathematical model (p. 54). The model in this case is the fundamental matrix (see Fundamental Matrix). The basic concept of the algorithm is that there is a set of data consistent with a mathematical model called the inliers and a set of data not consistent with the model called the outliers. RANSAC is non-deterministic in nature because it randomly chooses a set of points to create the model. RANSAC runs a set number iterations or until it finds a good set of inliers. The set of inliers that minimizes the error is the chosen set of data to represent the model. Thus the inliers in this case would be good feature points and outliers would be noisy and incorrect data.

Dense point matching
Once an accurate model has been established, a guided matching can occur. Guided matching usually consists of rectifying the images and comparing them to each other. Image rectification and comparison creates a set of dense point correspondences thus a better end result. This process can be repeated to get the most out of the images. This has yet to be implemented however.

Alternate Method
 Handpicked results, 37 correspondences
For simplicity, handpicked results will used. cpselect is the best way for getting manual sub-pixel accuracy point correspondences in MATLAB. Handpicked correspondences are used so possible errors that come from automatic feature detection are eliminated.

Camera Calibration
Camera calibration was done with the Camera Calibration Toolbox for MATLAB. The camera calibration process consists of taking images of a known calibration object. For the toolbox the calibration object is a checkerboard pattern. The user holds the calibration object in different positions while taking pictures of the object. These images are fed through the toolbox and it outputs the calibration information or better known as intrinsic parameters.

Intrinsic Parameters
The intrinsic parameters consist of focal length, principal point, and skew coefficient. Additionally, the toolbox can compute the distortions of the camera. With this information, the camera matrix K is built. The camera matrix allows a metric reconstruction of the scene up to a scale. Additionally, knowing the lens distortions of the camera will allow removal of distortion in the image correspondences. These variables are:

 Name Description Variable Dimensions Focal length Focal length in pixels fc 2x1 vector Principal point Principal point coordinates cc 2x1 vector Skew coefficient Skew coefficient defining the angle between the x and y pixel axes alpha_c 1x1 scalar Distortion coefficients Image distortion coefficients (radial and tangential distortions) kc 5x1 vector

The calibration matrix is computed (p157):

$K = $\left(\begin{array}{ccc} a_x & s & x_0 \\ 0 & a_y & y_0 \\ 0 & 0 & 1 \end{array}\right)$ = $\left(\begin{array}{ccc} fc(1) & alpha_c * fc(1) & cc(1) \\ 0 & fc(2) & cc(2) \\ 0 & 0 & 1 \end{array}\right)$$

Fundamental Matrix
The basic concept of the fundamental matrix is that it takes one space and projects onto another space. In this application the fundamental matrix takes the first image point set and projects it to the second image point set. The fundamental matrix has the essential matrix, which has the rotation and translation matrices that is needed to make the project matrices. It is computed by taking the Kronecker tensor product for every image correspondences and finding the SVD of the resulting matrix (p. 393)

Essential Matrix
In this case, $K_2$ and $K_1$ are equal because the same camera with the same setting were used. Thus, to recover the essential matrix [4, p. 257]:

$E = K_2^TFK_1=K^TFK$

The essential matrix must be projected into the essential space by:

$[U_E,E_E,V_E ] = SVD(E)$
$E = U_E * $\left( \begin{array}{ccc} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$ * V_E^T$

Extrinsic Parameters
The extrinsic parameters, rotation $R$ and translation $t$, can be recovered from the essential matrix $E$.

$W = $\left( \begin{array}{ccc} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$$

$Z = $\left(\begin{array}{ccc} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$$

$[U_E,E_E,V_E ] = SVD(E)$

$R = UWV^T or R = UW^T V^T$

$t = U_E*[0 0 1]^T or t = -U_E*[0 0 1]^T$

Thus now there are four sets of possible rotation and translation pairs. (p. 258 - 259)

The correct rotation and translation is the pair that creates (i.e. triangulates) points in front of both cameras. First, the project matrices have to be computed (see Projection Matrices), this will give $P_1$ and $P_2$. Next, one image pair has to be triangulated (see Triangulation), creating a 3D point $X$. The depth with a positive value for both project matrices and the 3D point will indicate the correct rotation and translation pair. This is done by (p162):

$X=(X,Y,Z,T)^T$

$P=[ M | p_4 ]$

$depth(X,P) = \frac{ sign(det(M)) * w }{T * ||m^3||}$

Projection Matrices
Computing the projection matrices is a simple task of putting all the information together. Note that the first projection matrix set to origin (0,0,0) with no rotation and translation.

$P_1 = $\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)$$

$P_2 = K * [R,t]$

Triangulation
In a perfect scenario, two rays extending from the points would intersect at a point in space. However, because of slight errors in the point correspondences the two points would never intersect or would intersect at the wrong point in space. The optimal triangulation algorithm brings the points closer to their respective epipolar lines (the plane that intersects the two cameras and the 3d point) so they intersect at a more accurate point in space [4, p318]. The final step of the algorithm is the actual triangulation. The algorithm is performed for every correspondence between the two images creating a point cloud.

The final step is the creation of the 3D model. This can be approached in various ways. For a simple mesh creation, MATLAB’s Delaunay function proved to yield good results. Texture for each triangle face can be taken from corresponding three points on either image. The issue with method is that it won’t work if any of the three points lay on a different plane. The better method is to create a dense point cloud that has the color information for every vertex. For output, a good model format is OBJ as it has an easy to follow textual representation for the model and is supported in many different model editors.

Model Creation
 Textured OBJ model viewed in MeshLab
Additionally, external applications such as MeshLab and Blender have proven useful. MeshLab has many point cloud to mesh construction algorithms under Filters > Remeshing, Simplification, and Reconstruction. Noteworthy reconstruction algorithms include Ball Pivoting Surface Reconstruction algorithm and Poisson Reconstruction. Texturing can be accomplished in Blender by UV mapping using the images.

## Sunday, February 21, 2010

### HTC Touch Pro Keyboard Fix

Update
Two months later my keyboard stopped working again. I followed my own fix but it didn't work. I bought a new keyboard from eBay for \$26 and installed it. No problems yet. Side note, I had to buy a Phillips size #000 screw driver to remove the four screws holding the keyboard to the sliding bracket. Again, this video on replacing the keyboard was useful.

Recently the keyboard on my Sprint HTC Touch Pro stopped working. I also didn't have the phone insurance plan (d'oh!) so I couldn't send it in to get it fixed without costing to much. So I did some research and found that when pushing down hard on the space key on the keyboard it makes the keyboard work again. This actually worked, however, it did not last. After a week of on and off keyboard functionality I decided it was time to dig deeper for a solution by opening the phone. Below the space key on keyboard is the keyboard's connector to the cellphone. It seems that the connector gets loose or the solder doesn't correctly make the connection. The solution is to push down on the solder so it makes the connection firm again.

Warning: Disassembling the phone WILL void your warranty and MAY damage your phone. Only do this if you feel comfortable dealing with electronics.

Tools
Torx screw driver with T-6 head
 (Top) Torx screw driver, with T-6 Head (Bottom) 3.0mm flathead screw driver

Before we begin, this video on keyboard replacement might be helpful in see how the phone looks on the inside. However, we will not be replacing the keyboard.

Directions
1. Turn off the cellphone, remove the back cover and remove the battery.
2. Unscrew the 4 Torx screws from the back. The screw in the top left has a sticker over it, removing this will most likely void the warranty.
3. Using the flathead screw driver, push down on the edges to pop out the keyboard. The keyboard should slowly push out on the other side. Work your way around the keyboard a few times. Alternatively, you can run the flathead screw driver or your finger nail around between the keyboard and the chrome frame until it pops out.
4. Once the keyboard is free, lift the side up next to the volume keys. Note: the keyboard frame is connected on BOTH sides, therefore it will not become fully detach, careful not to yank out the connector on the other side.
5. Lift up the orange cable directly below the space key.
6. Take the flathead screw driver and gently push down on the connector area. This should make the keyboard connection more firm.
7. Push the orange cable back down and put everything back.
Now the keyboard should be working again, enjoy. :-)

Images
 Keyboard cable (lift up)

 Keyboard connector (push down)

## Monday, November 23, 2009

In my probing of Notepad I've found a bug in the Find dialog:

OS: Windows XP SP 3 (Version 5.1.2600)
In the Find dialog box it allows one to enter a number of characters (unlimited?). However it only looks at the first 128 characters entered in the Find box. This could be misleading when somebody pastes a long string into the find dialog box. Additionally, when you reach the end of the search, when it prints out the string it cannot find it mentions only the first 128 characters. Find only does search for the first 128 characters, but it doesn't explicitly make it clear.

Below is an example when I tried entering 128 characters of 'a' then typing in 'ignored'. The image show how 'ignored' is not part of the search: finds the first 128 characters and when at the end of the find it displays that it cannot find the only the first 128 characters of the find string.

Thoughts & Fixes:
1. Allow only 128 characters to be entered into the Find text box.
2. When more than 128 characters get pasted into the Find text box have a message bubble explaining that the text was truncated.
3. Notepad++ seems to suffer from a similar issue in not explicitly making the user aware that its only searching for only first number of characters. However, Notepad++ actually cuts the string off after you execute the search, which implicitly tells the user that only the first number of characters were searched. Notepad only does this after you perform the search, close the Find dialog and reopen it, does it cut off the find string.

## Sunday, November 22, 2009

### Software Testing: Overview

Here's my condensing of Wikipedia's Software Testing and a few sub pages.

Software testing can’t make your code 100% bug free, but give more confidence it has less bugs.

Software Testing Topics
Functional vs. non-functional testing
Functional testing
• verify a specific action or function of the code
• Can the user do this?
• Does this particular feature work?
Non-functional testing
• May not be related to a specific function or user action (i.e., scalability or security)