My TV Interview on Rotana

C/C++ Goes-to Operator ??

Have you ever heard about the "Goes-to" operator (-->) in C and C++ ?
No? So, check out the following code:

#include <stdio.h>
int main()
{
    int x = 5;
    while (x --> 0) // X goes to 0
    {
        printf("%d ", x);
    }
}

The previous code compiles. Actually, there is no operator in C and C++ called "Goes-to". It's two separate operators; decrementing x and return its original value (-- operator), and then compare it if greater than zero (> operator).

To better understand, the while statement could be written as follows:
while ( (x--) > 0 ) .

A New Variant of Douglas–Peucker Algorithm (2/4) [Original Algo. MATLAB Implementation]

Previous Posts  

A New Variant of Douglas–Peucker Algorithm (1/4)

Original Douglas-Peucker Algorithm

The following algorithm description is taken from Wikipdeia [1] and CodeProject article by Elmar de Koning [2]. The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. This algorithm is also known under the names Douglas–Peucker algorithm, iterative end-point fit algorithm and split-and-merge algorithm.

The Douglas-Peucker algorithm uses a point-to-edge distance tolerance. The algorithm starts with a crude simplification that is the single edge joining the first and last vertices of the original polyline. It then computes the distance of all intermediate vertices to that edge. The vertex that is furthest away from that edge, and that has a computed distance that is larger than a specified tolerance, will be marked as a key and added to the simplification. This process will recurse for each edge in the current simplification, until all vertices of the original polyline are within tolerance of the simplification results. This process is illustrated below:

Initially, the simplification consists of a single edge. During the first step, the fourth vertex is marked as a key and the simplification is adjusted accordingly. During the second step, the first edge of the current simplification is processed. The maximum vertex distance to that edge falls below the tolerance threshold, and no new key is added. During the third step, a key is found for the second edge of the current simplification. This edge is split at the key and the simplification is updated. This process continues until no more keys can be found. Note that at each step, only one edge of the current simplification is processed.
This algorithm has a worst case running time of O(nm), and O(n log m) on average, where m is the size of the simplified polyline. As such, this is an output dependent algorithm, and will be very fast when m is small. To make it even faster, the Distance between points routine is applied as a pre-processing step.

MATLAB Implementation

function out_points = points_simplify_2d(points, epsilon)

  id_end = size(points,1);

  id_start = 1;

  % Indeces of points are not removed by Douglas-Peucker algorithm

  remaining_ids = true(id_end,1);

  % Call douglas_peucker_iteration (recursive function)

  [points remaining_ids] = douglas_peucker_iteration( ...
     points,epsilon,id_start,id_end, remaining_ids);

  out_points = points(remaining_ids,:);

end

function [points remaining_ids]  = douglas_peucker_iteration(points, epsilon, id_start, id_end, remaining_ids)

  % For the points (start + 1) to (end) -> next_points_relative is

  % relative coordinates from start point

  next_points_relative = bsxfun(@minus, points(id_start+1:id_end,:), 

     points(id_start,:));

  end_point_relative = next_points_relative(end,:)';

  % Efficient Method to get distances_from_start_end_line

  beta = (end_point_relative' *

     next_points_relative')./(end_point_relative'*end_point_relative);

  b = next_points_relative-bsxfun(@times,beta,end_point_relative)';

  distances_from_start_end_line = hypot(b(:,1),b(:,2));

  % Identify maximum distance and get its index

  [dmax dmax_id] = max(distances_from_start_end_line);

  dmax_id  = id_start + dmax_id; %ID of the edge point

  if dmax <= epsilon;
    remaining_ids(id_start+1:id_end-1) = false; 
  else  

    [points remaining_ids] = douglas_peucker_iteration( ...
       points,epsilon,id_start,dmax_id, remaining_ids);

    [points remaining_ids] = douglas_peucker_iteration( ...

       points,epsilon,dmax_id,id_end, remaining_ids);

  end

end

______________________________________________________________________
References:
[1] http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
[2] Polyline Simplification

A New Variant of Douglas–Peucker Algorithm (1/4) [Introduction]

The Ramer-Douglas-Peucker is a polyline simplification algorithm that uses a point-to-edge (point-to-line) distance tolerance “Epsilon”. The algorithm starts with a crude simplification that is the single edge (line) joining the first and last vertices (points) of the original polyline (polyline needed to be simplified). There is a variant of this algorithm already that allows it to produce a polyline with a fixed number of vertices “N”.

From software points of view, sometimes it’s preferred to have a fixed-size array to store a polyline vertices. Thus, the variant version of the Douglas-Peucker algorithm, that produces a fixed number of vertices “N”, is more convenient. However, from applications point of view, it doesn’t make sense to describe a simple polyline (rectangular area for example) with the same number of vertices that describe a complex-shaped one. This is why I’ve introduced my own version of the Douglas-Peucker algorithm, which I call a “Regularized” version.

My modified algorithm takes two pieces of data as inputs. The first is a predefined maximum number of vertices "N". The second is a tolerance "Epsilon". The algorithm returns n ≤ N vertices; it excludes the vertices that over-fit according to the predefined tolerance "Epsilon”. Those are the vertices that would have not been selected using the original Douglas-Peucker algorithm if it runs using the given "epsilon". A sample results of my variant of the Douglas–Peucker algorithm are shown in the coming table.

(A) N=50 , Epsilon=1.5 :	(B) N=50 , Epsilon=1.0 :
(C) N=100 , Epsilon=1.5 :	(D) N=10 , Epsilon=1.5 :

In the previous table, polyline (B) contains more vertices than polyline (A), because decreasing Epsilon allows more vertices to produce max edge distances higher than Epsilon, while these points still produce a polyline with number of vertices less than N. The resulted polyline in (C) is the same as (A), because increasing N, while having the same Epsilon will not produce new vertices that fits that Epsilon. Polyline in (D) contains fewer vertices than the polyline in (A), because the number of vertices in polyline (A) is greater than the N in (D).

In a coming posts, I will post the algorithms and MATLAB implementations for the three configurations:
- Original Douglas-Peucker algorithm.
- Variant of Douglas-Peucker algorithm (fixed number of simplified vertices "N").
- My Variant of Douglas-Peucker algorithm (with "N" and a tolerance "Epsilon").

Using OpenCV with Visual Studio

Step1. CMake:

CMake is used to make (build) your own libraries from the OpenCV source files and not to use the pre-built libraries. This allows to take advantage of the most advanced technologies OpenCV integrates into their library. You should build the ALL_BUILD project for both of the Debug and Release modes. Then, build the INSTALL project for both of Debug and Release modes. This step will prepare the folder: C:\openCV_build\visual_studio_10\install\ for you. In this tutorial, I assume that the chosen CMake build binaries directory is: C:\openCV_build\visual_studio_10\ .

-----------------------------------------------------------------------------------------------------------

Step2. Integration with Visual Studio 10 Project:

You can do this step globally once on your machine, or you can make it per project. In this tutorial, I choose to add the OpenCV libraries locally (per project), not to always clump all of the projects in my machine with OpenCV information.

At this point, you need to configure the Visual Studio project, so it can locate OpenCV headers and libraries. Go to the Project Properties (ALT+F7), and once the new window shows up do the following:

1. On the Configuration box, select All Configurations.
2. Open Configuration Properties > C/C++ > General, and edit the field Additional Include Directories to add these 3 paths (for the headers):C:\openCV_build\visual_studio_10\install\include\opencv
   C:\openCV_build\visual_studio_10\install\include\opencv2
   C:\openCV_build\visual_studio_10\install\include
3. Note that include\opencv is for the C interface of OpenCV and include\opencv2 if for the C++ interface. We are also adding the folder include to prevent our build from being broken by some headers of the C interface that refer to C++ headers as opencv2\core.
   
   
   
   
   
4. Then, add the path of the libraries on Configuration Properties > Linker > General, and on the Additional Library Directories field, add this: C:\openCV_build\visual_studio_10\install\x86\vc10\lib.
   
   
   
5. Finally, according to the complexity and need of the desired application, add the libraries that you need from:
   opencv_calib3d300.lib
   opencv_core300.lib
   opencv_features2d300.lib
   opencv_flann300.lib
   opencv_highgui300.lib
   opencv_imgcodecs300.lib
   opencv_imgproc300.lib
   opencv_ml300.lib
   opencv_objdetect300.lib
   opencv_photo300.lib
   opencv_shape300.lib
   opencv_stitching300.lib
   opencv_superres300.lib
   opencv_ts300.lib
   opencv_video300.lib
   opencv_videoio300.lib
   opencv_videostab300.lib
   
   So go to Configuration Properties > Linker > Input and add them:




Now, press F7 to Build Solution and you should see:
========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ========== .To be able to execute the application you'll need to modify the PATH environment variable of your system to add the location of OpenCV's DLLs. Add this to end of PATH:
;C:\openCV_build\visual_studio_10\install\x86\vc10\bin .

In the above discussion, you can just add a new environment variable called OPENCV_DIR and set the path: C:\openCV_build\visual_studio_10\install to it. And like that you will use $(OPENCV_DIR)\include, instead of: C:\openCV_build\visual_studio_10\install\include .

-----------------------------------------------------------------------------------------------------------

Step3. Debugging Images:

Just download NativeViewer, then open as text:

C:\Program Files (x86)\Microsoft Visual Studio 10.0\Common7\Packages\Debugger\autoexp.datto add the NativeViewer dll file path to it. In other words, under the [AutoExpand] section add the following line (modify the "E:\_PhD\Programs\NativeViewer_VS2010" with the link as in your machine):
cv::Mat=$ADDIN(E:\_PhD\Programs\NativeViewer_VS2010\NativeViewer_VS2010_v1.0.1\NativeViewer10.dll,CvMatViewer).You can also use Visual Studio 2012 or higher with Image Watch plug-in.

Like that, you will be able to see image during debugging as in the following image. Don't forget to hold down the Ctrl button before hovering over an image variable to see its image content.

Modified Condition/Decision Coverage (MC/DC - MCDC)

Consider the following C++ code, where x, y, and z are Integers :

if ( (A==1 || B==20) && C==30 ) {

    cout << "Decision is True!";

}

else {

    cout << "Decision is False!";

}.

We want to write a group of test cases T to test that the above Boolean expression: ( (A==1 || B==20) && C==30 ) is written correctly without inspecting the code with eyes. This task is very useful, especially when the Boolean expression is complicated. One example for a test case can be: If A, B, and C are at some moment are equal to 1, 20, and 30 respectively, the code within the first if condition should execute ("Decision is True!" to be printed) in case that the coder didn't commit a writing mistake within the Boolean expression. In simpler format :

A=1, B=20, C=30  ->  "Decision is True!".

The modified condition/decision coverage (MC/DC) is a code coverage criterion to achieve that testing. It allows generating test cases that can discover if :

• there is any missing condition that should be present, 
• there is any wrongly implemented "OR" or "AND" operation(s),
• or there is any wrongly inverted condition.

Firstly, let's define two concepts: Condition and Decision. We mean with Condition the atomic (indivisible, it's also called leaf-level) conditions. (A==1 || B==20) is a condition, but it's not atomic, while (A==1) is an atomic condition. On the other hand, Decision is the whole big condition under testing. It's ( (A==1 || B==20) && C==30 ) in our example code.

------------------------------------------------------------------------

For Condition Coverage:
(A==1), (B==20), and (C==30) are conditions. If the test cases in T guarantee that each condition is true in some test case and is false in another test case, we achieve condition coverage.

Example for a T that achieve condition coverage:

T = {

A=1, B=20, C=30 ->  "Decision is True!"  ,

A=0, B=0 , C=0  ->  "Decision is False!" }

------------------------------------------------------------------------

For Decision Coverage:

If the test cases guarantee that the Decision is true in some test case and is false in another test case, we achieve decision coverage. So, the above example T achieve decision coverage too.

------------------------------------------------------------------------

For Modified Condition/Decision Coverage:

For each atomic condition X, there should be two test cases T₁ and T₂ in T that achieve the following three conditions:

• In T₁ X is true, while it's false in T₂.
• In T₁, the Decision is true, while it's false in T₂.
  Or the opposite.
• T₁ and T₂ are common for all the conditions other than X.

For example:

T = {

A=0, B=0 , C=30 ->  "Decision is False!" ,

A=0, B=20, C=30 ->  "Decision is True!"  ,
A=0, B=20, C=0  ->  "Decision is False!" ,
A=1, B=0 , C=30 ->  "Decision is True!"  }

In the previous example test cases, for the condition (A=0),
(A=0, B=0 , C=30 ->  "Decision is False!") is T₁, and 
(A=1, B=0 , C=30 ->  "Decision is True!") , is T₂. Note that, for any Boolean expression there will be at least n+1 test cases to achieve Modified Condition/Decision Coverage, where n is the number of conditions.

Entropy .. Simply !

In information theory, entropy is the average amount of information contained in each message received. Let's dig into an example directly,
the four possible outcomes (events) that could occur if you flipped a coin twice (experiment) are:
Head then Head , Head then Tail , Tail then Tail , and Tail then Head .

Note that the four outcomes (sample space) are equally likely, so each probability should be equal to 1/4 :
P(X₁=Head & X₂=Head) = 1/4 ,
P(X₁=Head & X₂=Tail) = 1/4 ,
P(X₁=Tail & X₂=Tail) = 1/4 , and
P(X₁=Tail & X₂=Head) = 1/4 .

The entropy for the previous example is given by:

H(X)=−ΣiP(x)log2[P(x)]=

 = - (1/4) log₂(1/4) - (1/4) log₂(1/4) - (1/4) log₂(1/4) - (1/4) log₂(1/4) = 2.

This means that you need 2 bits to store the actual status at any moment that comes out when conducting that experiment (event).
---------------------------------------------------------------------------------------------
Let's have another simple example. If we expect if the sun will rise tomorrow or not (experiment), we obtain two possible outcomes (sample space):
P(SunRisesTommorrow) = 1 and
P(SunWontRiseTommorrow) =0 .
  

So, the entropy is : = - (1) log₂(1) - (0) log₂(0)  = 0.

This means that we don't need any bits to store the actual status of that experiment, because we are 100% sure that tomorrow the sun will rise (P(SunRisesTommorrow) = 1).
---------------------------------------------------------------------------------------------
"The entropy of the unknown result of the next toss of the coin is maximized if the coin is fair (that is, if heads and tails both have equal probability 1/2). This is the situation of maximum uncertainty as it is most difficult to predict the outcome of the next toss; the result of each toss of the coin delivers one full bit of information.
However, if we know the coin is not fair, but comes up heads or tails with probabilities p and q, where p ≠ q, then there is less uncertainty. Every time it is tossed, one side is more likely to come up than the other. The reduced uncertainty is quantified in a lower entropy: on average each toss of the coin delivers less than one full bit of information." Wikipedia

C Function with Variable Number of Arguments

One usually need to implement a function where the number of arguments (parameters) is not known, or is not constant, when the function is written. Just like the printf function. The following example shows that in terms of code:

int f(int, ... ) {

        .

        .

        .

}

int g() {

        f(1,2,3);

        f(1,2);

}

Let's consider a simple example, we need to implement a function GetSum that calculates the summation of any number of integers.

So, such function takes variable number of arguments.

The first one is Size: the number of integers to calculate the summation for.

Then it takes each integer of the numbers to be added as a separate parameter.

You can call it to calculate the summation of two numbers (4+30), like :

GetSum(2, 4, 30); /* returns 34 */

Or to calculate the summation of 5 numbers (7+10+1+15+3), like :

GetSum(5, 7, 10, 1, 15, 3); /* returns 36 */

The implementation of GetSum is as follows. The comments describe everything:

#include <stdarg.h>

int GetSum(int Size, ...)

{

    int Sum = 0.0;

    

    // 1- Create Variable List

    va_list variable_list;

    // 2- Initialize variable_list to retrieve data

    //      starting from the address of the parameter Size

    va_start(variable_list, Size);

    // 3- Access all the arguments assigned to variable_list

    for (int Index = 0; Index < Size; Index++) {

       Sum += va_arg(variable_list, int);

    }

    // 4- Clean memory reserved for variable_list

    va_end(variable_list);

    return Sum;

}

Hidden Markov Model HMM .. Simply ! (1/3)

In this series of tutorials, I will explain very important concepts about the probability theory in a simple way.We will simplify the concept and mathematics of Hidden Markov Models (HMM). It is named after the Russian mathematician Andrey Markov. Almost all present day large vocabulary continuous speech recognition (LVCSR) and text/handwriting recognition systems are based on HMMs! HMMs lie at the heart of almost all of the modern successful speech and text recognition solutions.

In this tutorial, we will explain what a Markov Models is and what are the probability theory concepts that are related to it. This topic is very essential to understand HMM. For this purpose, let's try to figure out this problem: we need to make a probability model that we can use to predict the weather in Cairo for tomorrow.

    

For the weather state, let's assume we only have three possibilities:

• State 1: Sunny
• State 2: Cloudy
• State 3: Rain or Snow (Rain/Snow)

By carefully examining the weather of Cairo for a long period of time, we found following weather change pattern:

--------------------------------------------------------------------------------------------

What you see in the previous image is a Markov Model diagram that can be used to predict the weather in Cairo. In that model:

if today is Sunny, the probability of having a Sunny day tomorrow = 0.6,

the probability of having a Cloudy day tomorrow = 0.3,

and the probability of having a Rain/Snow tomorrow = 0.1. It's logic that the summation of these values is equal to one, because they cover all the three possibilities of tomorrow's weather given that today is Sunny. The summation of outgoing edge weights from every state should be one.

Also, note that the weather of tomorrow depends on today and is totally independent on the weather of yesterday. In other words, the next state depends only on the current state and not the previous one(s). A stochastic process (a system whose state is non-deterministic: random) has the Markov property if the conditional probability distribution of future states of the process (conditional on both past and present values) depends only upon the present state, not on the sequence of events that preceded it. A process with this property like our process is called a Markov process.

Our weather problem looks simple, we can estimate the different weather probabilities for some days easily. But because that the purpose of these tutorials is to explain HMM which is more complex. We need to define properties, like the ones in the previous two paragraphs, in terms of mathematics. So that when things are getting complected, we have some nice equations that can resolve it. So now, let's make some definitions concerning Markov Model:

• Number of States :
  N, where N=3 in the previous weather example.

• 1st order Markov assumption :
  P( S_t = X | S_t-1 = Y | S_t-2 = Z | S_t-3 = W | ... | .... ) = P( S_t = X | S_t-1 = Y ) ,
  In words,
  the probability of having a state X at some day (t)
  giventhat in the previous day (t-1) it was state Y,
  and that the day before it (t-2), it was state Z,
  and that the day before before it (t-3), it was state W,
  and that the day before before before it (t-4), it was state ....
  and that the day before before before before it (t-5), it was state ....
  ....
  is equal to
  the probability of having a state X at some day (t)
  given
  that in the previous day (t-1) it was state Y.

• Stationary :
  P( S_t = X | S_t-1 = Y ) = P( S_t+1 = X | S_t+1-1 = Y ) ,
  In words, the probability of having a state X at some day (t) given that in the previous day it was state Y,is the same value regardless in which day am I.

• State Transition Matrix :
  , Where:
  a_xy = P( S_t = Y | S_t-1 = X ), 1 ≤ x,y ≤ N , with constraint a_xy ≥ 0,
  

• Initial state probability:
  πi = P( S₁ = X )
  In words, πi. is the provability of having the first day (the very initial first day, as if there are no days before it) to be state X.

• Conditional Property:
  P( S_t = X , S_v = Y ) = P( S_t = X | S_v = Y ) * P( S_v = Y )
  In words,
  the probability of having a state X at some day t
  and (means that both events should happen)
  having a state Y at some other day v,
  is equal to
  the probability of having a state X at some day t
  given that we (will) have a state Y at some other day v
  multiplied by
  the probability of having a state Y at the day v.

• Chain Rule:
  P( S₁ = X | S₂ = Y | S₃ = Z | ... | .... | S_T-1 = W | S_T = U ) =
  P( S₁ = X ) * P( S₂ = Y | S₁ = X )
      * P( S₃ = Z | S₁ = X,S₂ = Y ) * ... * P( S_T = U | S₁ = X,S₂ = Y,S₃ = Z, ... ,S_T-1 = W )
  And using the 1st order Markov assumption definition/property:
  = P( S₁ = X ) * P( S₂ = Y | S₁ = X ) * P( S₃ = Z | S₂ = Y ) * ... * P( S_T = U | S_T-1 = W )

--------------------------------------------------------------------------------------------

Now, let's go back to our previous Cairo weather example, we will have a state transition matrix as follows :

, and let's say we have an initial state properties as follows : πi = {0.9, 0.08 , 0.02}. Note that the summation of the previous group should be equal to one. We need to answer a question:
" What is the probability that the weather for the next five days will be: “sunny-rain-sunny-cloudy-cloudy” when today is sunny? ". We should remember that sunny is state 1, cloudy is state 2, and rain/snow is state 3. The solution to that question is as follows:

P(O | model) = P (S₁ = 1 , S₂ = 1, S₃ = 3, S₄ = 1, S₅ = 2, S₆ = 2 | model)
  =  P (S₁ = 1) * P (S₂ = 1 | S₁ = 1) * P (S₃ = 3 | S₂ = 1) *
                          P (S₄ = 1 | S₃ = 3) * P (S₅ = 2 | S₄ = 1) * P (S₆ = 2 | S₅ = 2)
 = π1 * S₁₁ * S₁₃* S₃₁ * S₁₂ * S₂₂ = 0.9 * 0.6 * 0.1 * 0.4 * 0.3 * 0.2 = 0.001296,
which means: 0.1296 % !

In the next article we will explain about Hidden Markov Models.
I will be glad to answer your questions or hear your feedback in the comments.