The Extended Euclidean Algorithm

Try this!! You will definitely find it interesting.
Consider two integers m and n. Find two integers a and b such that m*a + n*b = gcd(m,n)

Example 1: m = 65; n = 40

Step 1: The (usual) Euclidean algorithm:
(1) 65 = 1*40 + 25
(2) 40 = 1*25 + 15
(3) 25 = 1*15 + 10
(4) 15 = 1*10 + 5
     10 = 2*5  + 0    (Do this until remainder = 0)
Therefore: gcd(65; 40) = 5.

Step 2: Using the method of back-substitution:
5 (4) = 15 - 10
   (3) = 15 - (25 - 15) = 2*15 - 25
   (2) = 2(40 - 25) - 25 = 2*40 - 3*25
   (1) = 2*40 - 3(65 - 40) = 5*40 - 3*65

Conclusion: 65(-3) + 40(5) = 5.



Example 2: m = 1239; n = 735
Step 1: The (usual) Euclidean algorithm:
(1) 1239 = 1*735 + 504
(2)  735  = 1*504 + 231
(3)  504  = 2*231 + 42
(4)   23   = 5*42 + 21
       42   = 2*21 + 0
Therefore: gcd(1239; 735) = 21.

Step 2: Using the method of back-substitution:
21 (4) = 231 - 5*42
     (3) = 231 - 5(504 - 2*231) = 11*231 - 5*504
     (2) = 11(735 - 504) - 5*504 = 11*735 - 16*504
     (1) = 11*735 - 16(1239 - 735) = 27*735 - 16*1239

Conclusion: 1239(-16) + 735(27) = 21.

Install OpenCV 2.0 on Windows

          To install OpenCv on your Windows, you need Microsoft Visual Studio 2008 and CMake. Remember, this process is little bit complicated and lengthy. But, it's worth of it.

The process is explained in detail in this document.

Install OpenCV and run the sample code. In the next post, I will show some simple OpenCV programs and also
how to install OpenCV on Linux platform.

Image Processing: Matlab vs OpenCV

                     Do you get bored by the speed of Matlab while processing images or videos? Then try OpenCV. It is easy to use and more importantly, almost 20 times faster than Matlab Image Processing Toolbox. It is mainly used for real time computer vision. It is an open source software and you can download OpenCv for free here .

      OpenCV stands for Open Source Computer Vision Library. It is a library of programming functions. This library was developed by Intel and is now supported by Willow Garage. It is free for use under the open source BSD license. The library is cross-platform. It focuses mainly on real-time image processing.
      
        The library is written in C and C++ and runs under Linux, Windows and Mac OS X. There is active development on interfaces for Python, Ruby, Matlab, and other languages. OpenCV was designed for computational efficiency and with a strong focus on real time applications. OpenCV is written in optimized C and can take advantage of multi-core processors.
       
        The OpenCV library contains over 500 functions that span many areas in vision, including factory medical imaging, security, user interface, camera calibration, stereo vision, and robotics. Because computer vision and machine learning often go hand-in- hand, OpenCV also contains a full, general-purpose Machine Learning Library (MLL). This sub-library is focused on statistical pattern recognition and clustering.

         In the future posts, I will share my experience of using OpenCV, both on Windows and Linux platforms.