Take an encryption case for example. You are given a sequence of number, 6 3 1 7 5 8 9 2 4, which is encrypted. To get the real meaning, we delete 6 and put 3 to the end, and the number becomes 1 7 5 8 9 2 4 3. Then we delete 1 and put 7 to the end, the number becomes 5 8 9 2 4 3 7. We delete 5 and put 8 to the end, getting 9 2 4 3 7 8... Eventually the numbers get deleted are 6 1 5 9 4 7 2 8 3.
Queue is a special structure, which only allows the elements at head to be deleted, which is called pop out. It only allows to input new elements at tail, means pop in. When head == tail, the queue is empty.
What is stack? Suppose we have a bucket, and we can only put in one ball each time. We now put in ball 2, 1, 3. If you want to take out ball 2, then you have to take ball 3 out first, and then ball 1.
We can use stack to determine whether a string is equal no matter if you read it forward or backward.
Now let's talk about node. We often use array to store numbers, but it is not always convenient. For example, we have a sequence of numbers, arranged in ascending order, 2 3 5 8 9 10 18 26 32. If we want to input 6 and ensure the new sequence is still in ascending order, then we have to move all the numbers after 8 if we use array.
What is node? Node is 2-3-5-8-9-10-18-26-32. If we want to input 6, we just need 2-3-5-6-8-9-10-18-26-32. Each node has two parts, one stores the data, using an int. The other stores the address of next data, using pointer.
An alternative way to realize node is to use array to simulate it. Suppose we have the data 2 3 5 8 9 10 18 26 32, we need to use another array called right to store the position of the number on the right of the data 2 3 4 5 6 7 8 9 0. For instance, right[1] = 2, means the number on the right of data[1] is in data[2]. right[9] = 0, means there is no number of the right of 9.
If we want to input 6, we only need to put it at the end, data[10] = 6. Then we need to change right[3] = 10, means we put the number on the right of data[3] to data[10]. We also need to set right[10] = 4, means the number right to data[10] is in data[4].
Friday, 31 July 2015
MonoSLAM for dummies
The basic idea about SLAM is that if I were a robot, and I know two fixed points: (x1, y1) and (x2, y2). I now can see point1, and the measurement tells me it is 5 m away from me. When I turn my head for 30 degrees, I can see point2, and the measurements tell me it is 10m away. As a result of knowing my relative position with respect to point1 and point2, I can localize myself.
But here comes the question. I have to look back to see point1 and point2 every time I move forward, to know where I am. This kind of looking back is very stupid. So, a smart PhD student comes up with a solution: as soon as I know where I am with respect to point1, point2, I add more points: point3, point4... because I know the coordinate of myself, I can measure the location of these points (mapping). I could use those points afterwards for localization.
Therefore, SLAM means knowing my localization and the coordinates of the fixed points (feature mapping). Because SLAM introduces noise no matter when measuring distance or calculating the rotation, traveled distance, SLAM requires Kalman filter.
MonoSLAM also refers to real time structure from motion. The fixed points are the visual features, and measuring distance becomes match feature and then triangulate.
MonoSLAM is implemented in MATLAB here. The authors introduce MonoSLAM in the following way. SLAM in a 3D environment - Need of 3D landmarks - Camera based method - use of visual 2D interest points - camera gives 2D interest points - no depth information - how to get depth? - by using camera motion - How to estimate camera motion - by using 3D landmarks.
Therefore, 3D landmark = 2D interest point + depth.
At the beginning, a few initial landmarks must be provided for initialization, otherwise the camera motion cannot be estimated. After the initialization phase, an iterative process begins. Step 1: 2D interest points must evolve into 3D landmarks when the estimate of their depth is good enough. Step 2: 3D landmarks contribute to the estimation of the state, including camera and the map.
The camera and map state is estimated through an EKF. After initialization, this filter performs a model based prediction, compares it to the measurements (camera data), and thus applies a correction on the global state according to the innovation.
To use camera data, we have to know its resolution, focal length, CMOS sensor dimension, and thus we need to perform a calibration step, such as the MATLAB toolbox.
The landmarks could be initialized manually, or by using an object of known size at the beginning.
Since we use EKF, we need to have a model, and the only model we can have for the camera is a kinematic one, instead of a dynamic one. This model allows only constant velocity movement. However, the camera may not move in this way. Hence we have to add a noise to allow for changes in direction or speed. This is necessary for the EKF to assess the confidence into its estimates.
A common noise model is the additive noise model, where random gaussian noise is added on each state component. But here we use a non linear, acceleration based noise model. To enable several trajectories around the previous one, we consider the linear and angular accelerations to be given by random zero mean gaussian variables. The standard deviation of these variables allows us to tune how uneven the motion can be.
The prediction step randomly chooses one trajectory among these possibilities, and if necessary the correction step will bring the system back in tracks.
Landmarks are identified from interest points. The Shi-Tomasi detector is used to define salient points. The detection is based on local extrema of the gradient analysis of 15x15 pixels patches. The eigenvalues of the matrix are used to assess the quality of a potential interest point, through a threshold. When a new interest point is identified, it is attached to its neighborhood, namely its 15x15 patch, to describe this point. The patch is normalized to increase the detection robustness for illumination change.
Since there is no depth information from a single image, we need to use motion to recover the depth. This is done using particle filter. When an interest point is selected, we only know that this point belongs to a certain line called the epipolar line. To estimate where the point lies on the epipolar line, the line is uniformly sampled by a given number of particles, where each particle represents a depth hypothesis. A maximal depth hypothesis related to the size of the environment limits the search zone.
When an interest point has been registered, meaning that its patch and epipolar line are known, the algorithm tries to match it in the subsequent pictures. An interest point without any depth information is tracked using correlation over a window. The size of the window is constant, defied by a maximal acceleration in terms of pixels. Interest points moving out of the image or weakly matched are discarded.
During the tracking, after the correlation has matched an interest point, all the particles associated to this point are re-projected in the picture. Resampling is performed to promote hypothesis best-linked to the correlation result, and 25% of the particles are resampled uniformly to avoid early convergence. When the variance of the depth hypotheses shrinks below a threshold, the estimation is considered reliable. The interest point is then attached a depth and becomes a landmark, with a large uncertainty along the epipolar line to allow the EKF to modify its position easily if necessary.
Compared to the interest point management (initialization, tracking, depth estimation and upgrade as landmark), landmark tracking is much easier. The EKF prediction gives an estimate of the camera position and orientation, as well as uncertainties on these quantities and on the landmarks position. The position and orientation of the camera, relative to the landmarks position, allow us to predict how the landmarks will be projected onto the image plane, along with an uncertainty area. Both the uncertainty of the camera position and orientation and the uncertainty of landmark position are taken into account to compute this uncertainty area. The larger the uncertainty is, the wider the search area is in the new picture. The the search is simply performed by correlation within this area. The difference between the EKF prediction and the camera observation gives the innovation signal of the filter.
When the algorithm is running, at least one landmark must always be visible. Thus, as soon as the number of visible landmarks falls below a chosen number, a search procedure is launched, in order to identify new interest points. This is achieved by searching interest points in randomly drawn windows. The only constraint on these windows is they have to be far away from the currently tracked landmarks and interest points. Otherwise, no effort is spent in trying to pick up interest points in the most useful place for the algorithm.
The innovation signal is at the core of the EKF correction step, which affects the whole state vector. We previously explained how the innovation signal is obtained, without any details concerning the projection.
The simple pinhole camera model is used to perform reprojection. No distortion correction is applied here. For a landmark yi described by its coordinates in the world frame, we have to express its position relatively to the camera.
Correction is based on the innovation. A simple additive noise is finally added to the observation model, which enables us to tune the confidence of the EKF towards the observations. To increase the robustness of the correction algorithm, landmarks weakly matched (bad correlation results) or unmatched (not seen when tey are predicted to be seen) along several frames are removed from the map. EKF is very likely to be lost if the landmark association is bad.
But here comes the question. I have to look back to see point1 and point2 every time I move forward, to know where I am. This kind of looking back is very stupid. So, a smart PhD student comes up with a solution: as soon as I know where I am with respect to point1, point2, I add more points: point3, point4... because I know the coordinate of myself, I can measure the location of these points (mapping). I could use those points afterwards for localization.
Therefore, SLAM means knowing my localization and the coordinates of the fixed points (feature mapping). Because SLAM introduces noise no matter when measuring distance or calculating the rotation, traveled distance, SLAM requires Kalman filter.
MonoSLAM also refers to real time structure from motion. The fixed points are the visual features, and measuring distance becomes match feature and then triangulate.
MonoSLAM is implemented in MATLAB here. The authors introduce MonoSLAM in the following way. SLAM in a 3D environment - Need of 3D landmarks - Camera based method - use of visual 2D interest points - camera gives 2D interest points - no depth information - how to get depth? - by using camera motion - How to estimate camera motion - by using 3D landmarks.
Therefore, 3D landmark = 2D interest point + depth.
At the beginning, a few initial landmarks must be provided for initialization, otherwise the camera motion cannot be estimated. After the initialization phase, an iterative process begins. Step 1: 2D interest points must evolve into 3D landmarks when the estimate of their depth is good enough. Step 2: 3D landmarks contribute to the estimation of the state, including camera and the map.
The camera and map state is estimated through an EKF. After initialization, this filter performs a model based prediction, compares it to the measurements (camera data), and thus applies a correction on the global state according to the innovation.
To use camera data, we have to know its resolution, focal length, CMOS sensor dimension, and thus we need to perform a calibration step, such as the MATLAB toolbox.
The landmarks could be initialized manually, or by using an object of known size at the beginning.
Since we use EKF, we need to have a model, and the only model we can have for the camera is a kinematic one, instead of a dynamic one. This model allows only constant velocity movement. However, the camera may not move in this way. Hence we have to add a noise to allow for changes in direction or speed. This is necessary for the EKF to assess the confidence into its estimates.
A common noise model is the additive noise model, where random gaussian noise is added on each state component. But here we use a non linear, acceleration based noise model. To enable several trajectories around the previous one, we consider the linear and angular accelerations to be given by random zero mean gaussian variables. The standard deviation of these variables allows us to tune how uneven the motion can be.
The prediction step randomly chooses one trajectory among these possibilities, and if necessary the correction step will bring the system back in tracks.
Landmarks are identified from interest points. The Shi-Tomasi detector is used to define salient points. The detection is based on local extrema of the gradient analysis of 15x15 pixels patches. The eigenvalues of the matrix are used to assess the quality of a potential interest point, through a threshold. When a new interest point is identified, it is attached to its neighborhood, namely its 15x15 patch, to describe this point. The patch is normalized to increase the detection robustness for illumination change.
Since there is no depth information from a single image, we need to use motion to recover the depth. This is done using particle filter. When an interest point is selected, we only know that this point belongs to a certain line called the epipolar line. To estimate where the point lies on the epipolar line, the line is uniformly sampled by a given number of particles, where each particle represents a depth hypothesis. A maximal depth hypothesis related to the size of the environment limits the search zone.
When an interest point has been registered, meaning that its patch and epipolar line are known, the algorithm tries to match it in the subsequent pictures. An interest point without any depth information is tracked using correlation over a window. The size of the window is constant, defied by a maximal acceleration in terms of pixels. Interest points moving out of the image or weakly matched are discarded.
During the tracking, after the correlation has matched an interest point, all the particles associated to this point are re-projected in the picture. Resampling is performed to promote hypothesis best-linked to the correlation result, and 25% of the particles are resampled uniformly to avoid early convergence. When the variance of the depth hypotheses shrinks below a threshold, the estimation is considered reliable. The interest point is then attached a depth and becomes a landmark, with a large uncertainty along the epipolar line to allow the EKF to modify its position easily if necessary.
Compared to the interest point management (initialization, tracking, depth estimation and upgrade as landmark), landmark tracking is much easier. The EKF prediction gives an estimate of the camera position and orientation, as well as uncertainties on these quantities and on the landmarks position. The position and orientation of the camera, relative to the landmarks position, allow us to predict how the landmarks will be projected onto the image plane, along with an uncertainty area. Both the uncertainty of the camera position and orientation and the uncertainty of landmark position are taken into account to compute this uncertainty area. The larger the uncertainty is, the wider the search area is in the new picture. The the search is simply performed by correlation within this area. The difference between the EKF prediction and the camera observation gives the innovation signal of the filter.
When the algorithm is running, at least one landmark must always be visible. Thus, as soon as the number of visible landmarks falls below a chosen number, a search procedure is launched, in order to identify new interest points. This is achieved by searching interest points in randomly drawn windows. The only constraint on these windows is they have to be far away from the currently tracked landmarks and interest points. Otherwise, no effort is spent in trying to pick up interest points in the most useful place for the algorithm.
The innovation signal is at the core of the EKF correction step, which affects the whole state vector. We previously explained how the innovation signal is obtained, without any details concerning the projection.
The simple pinhole camera model is used to perform reprojection. No distortion correction is applied here. For a landmark yi described by its coordinates in the world frame, we have to express its position relatively to the camera.
Correction is based on the innovation. A simple additive noise is finally added to the observation model, which enables us to tune the confidence of the EKF towards the observations. To increase the robustness of the correction algorithm, landmarks weakly matched (bad correlation results) or unmatched (not seen when tey are predicted to be seen) along several frames are removed from the map. EKF is very likely to be lost if the landmark association is bad.
Tuesday, 28 July 2015
Reduce PDF size in Ubantu
According to this post, we can use Ghostscript to reduce the pdf size.
gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -dNOPAUSE -dQUIET -dBATCH -sOutputFile=foo-compressed.pdf foo.pdf
Sunday, 19 July 2015
Latex table
In latex table, if you put \caption before \begin, then the caption will appear at the top. If you put \caption after \begin, the caption will appear below the table, which is the norm for most papers. Moreover, \label should be in the same line with \caption.
Wednesday, 15 July 2015
默写欧洲/英国的侦探们
一个景点的知名度往往能够从它对所在地的影响上面看出来。而大名鼎鼎的福尔摩斯博物馆更是从地铁站就开始了它的宣传。到达以福尔摩斯居住地命名的贝克街地铁站后，看到那里的仿古建筑，仿佛瞬间回到了大侦探所在的维多利亚时代。
带着这种穿越的感觉走出站口,激动的发现福尔摩斯本人就伫立在门口,叼着烟斗穿着斗篷和鹿皮帽子,仿佛正在思考着案件. 看到他的雕像,想必大多数福迷都会内心中无比的激动,心跳加速,面目通红,手舞足蹈,恨不得要个签名啥的.
福尔摩斯博物馆收费6英镑,平均每层2英镑,每个房间1.5英镑,估计是所有博物馆里面每层和每间房最贵的之一了.
带着这种穿越的感觉走出站口,激动的发现福尔摩斯本人就伫立在门口,叼着烟斗穿着斗篷和鹿皮帽子,仿佛正在思考着案件. 看到他的雕像,想必大多数福迷都会内心中无比的激动,心跳加速,面目通红,手舞足蹈,恨不得要个签名啥的.
福尔摩斯博物馆收费6英镑,平均每层2英镑,每个房间1.5英镑,估计是所有博物馆里面每层和每间房最贵的之一了.
Tuesday, 14 July 2015
Something about graduate studies July 14
Here is an interesting talk on what qualities are important for PhD. As far as I can see, the most important one in the eyes of supervisors is curiosity and persistence.
Here is a talk on how to write a good paper. The most important thing is to make it very clear what are the contributions, and the problem you are solving, the context of the problem, solution, and how your paper improves upon previous work.
Organization plays a vital part, as both that talk and this point out. A paper should start by telling the audience which problem you are addressing, and why they should care about it. Moreover, you should spell it out explicitly the implications of your solution. Then present the reasons why previous solution are not satisfactory. Next, explain your own solution, and do remember to compare it with other solutions.
What is often not noticed is that, the paper should be understandable for those who read it in a hurry. To achieve this, use figures and captions to tell the story. The figure captions should be self-contained and the caption should tell the reader what to notice about the figure.
The most common reasons for rejections include
Promise more than what is delivered
Exclusion of important references
Main idea is not new
The results are similar to previous work
The results are too different from previous work
Start writing the paper early and re-write it until it is good!
Here is a talk on how to write a good paper. The most important thing is to make it very clear what are the contributions, and the problem you are solving, the context of the problem, solution, and how your paper improves upon previous work.
Organization plays a vital part, as both that talk and this point out. A paper should start by telling the audience which problem you are addressing, and why they should care about it. Moreover, you should spell it out explicitly the implications of your solution. Then present the reasons why previous solution are not satisfactory. Next, explain your own solution, and do remember to compare it with other solutions.
What is often not noticed is that, the paper should be understandable for those who read it in a hurry. To achieve this, use figures and captions to tell the story. The figure captions should be self-contained and the caption should tell the reader what to notice about the figure.
The most common reasons for rejections include
Promise more than what is delivered
Exclusion of important references
Main idea is not new
The results are similar to previous work
The results are too different from previous work
Start writing the paper early and re-write it until it is good!
Saturday, 11 July 2015
Latex flowchart figure
Many times a figure is too long for a paper, such as a flowchart. In this case, we have to put the figure horizontally to save space, like the overview in the HOG paper. To do this, we need to use \begin{figure*} instead of \begin{figure}, to ensure that the figure spans two columns. Moreover, we use [t!] to put the figure at the top of the page. Sometimes the figure appears at the next page of where it is referenced. To solve this, place the figure \begin{figure*}[t!] somewhere before it is referenced, eg in the previous page. It turns out that the figure position has nothing to do with where it is referenced, but depends on where it is included.
Subscribe to:
Posts (Atom)