tag:blogger.com,1999:blog-39968484160746375212024-02-19T13:25:12.656+05:30Mathematics for Computer Graphics & Image processingA continuous journeytesthttp://www.blogger.com/profile/03784579986960576423noreply@blogger.comBlogger90125tag:blogger.com,1999:blog-3996848416074637521.post-57311218125366194382016-05-12T11:48:00.001+05:302016-05-13T18:25:32.764+05:30Thoughts about Regression analysis<div class="tr_bq">
Recently i watched a video about regression and probability, Here i am presenting some information from that.</div>
<br />
Regression analysis is about establishing relationship between variables. That means there will be set of independent variables and corresponding dependent variables.<br />
<br />
Example<br />
<br />
let us denote price of a house using variable Y and factors affecting the price, such as area,age,location using variable X.<br />
<br />
To make everything more simpler, let us take only the area of house as the independent variable, so there will be only one feature. Now we need to model the price (Y) of house. So that we can predict the price of an house if someone gives us the area. We can use the following simple equation to model that<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><b>H(t0,t1,i) = t0 + t1 * X(i)</b> -----------------> <b> EQ(1)</b></span><br />
<br />
t0 and t1 are constants.. ( when we have multiple factors, deciding the price other than area then it is possible to add more features to equation like <b> 't0 + t1 * X1 + t2 * x2 + t2 * X1 * X2'</b> or so on)<br />
<br />
X(i) indicate sample number. That means if we have 100 data set containing 'area - price' pairs then X(5) will indicate the 5th area from the given data set.<br />
<br />
If we plot <b>EQ1(1)</b>, it will be a line for sure. So basically we are trying to find a line which will match with the expected set of house prices. See the following image.. where you can see a line which can be used to predict house price on a X value.<br />
<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLAgVEHtuu5plclS0Jr1NnPqs1-cNDT1ax4JtEmj0EVuexQMECn3XpiG-FVTJFaatWJ6Cl0Rt3QQyckKIqXZOglnprqLvVysyK8Y2O30LqrLTMQLYGXsHK4QwRg6i6SnEKFruEV2M_04s/s1600/idea.png" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLAgVEHtuu5plclS0Jr1NnPqs1-cNDT1ax4JtEmj0EVuexQMECn3XpiG-FVTJFaatWJ6Cl0Rt3QQyckKIqXZOglnprqLvVysyK8Y2O30LqrLTMQLYGXsHK4QwRg6i6SnEKFruEV2M_04s/s400/idea.png" /></a><br />
<br />
<br />
<b>EQ(1)</b> can be changed to higher degrees to achieve more complex predictions. But simply adding more degrees will not help much. You also need to define the model in a more meaningful way.<br />
<br />
Back to problem,<br />
Now we need to find values for<b> 't0</b>' and<b> 't1</b>' such that it will help to form a meaningful model.<br />
For that we need to define cost function<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSmJ2PaGYm5QBMY4IBpFRBa3bS6jhslDSDgTr944B0ZR3WYf-ETts0bxPh8UoP4BmHRX76lJcCsiLoQJ0_jCRc6p-Una4vLMi39g-3-BJeJnuPbjatYQMu69zNoKDaJ56JZ1aswpmDZyk/s1600/cost_function.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="73" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSmJ2PaGYm5QBMY4IBpFRBa3bS6jhslDSDgTr944B0ZR3WYf-ETts0bxPh8UoP4BmHRX76lJcCsiLoQJ0_jCRc6p-Una4vLMi39g-3-BJeJnuPbjatYQMu69zNoKDaJ56JZ1aswpmDZyk/s320/cost_function.png" width="320" /></a><br />
<br />
------------- <b>EQ(2)</b><br />
<b><br /></b>
<b><br /></b>
<b><br /></b>
From <b>EQ(2) </b>we can see that , it is actually finding the sum of squared difference between expected value and our defined model (here it is based on line equation).<br />
<br />
Aim must be to minimize <b>EQ(2) </b>, more we can minimize, less error will be , and our predicted line will be aligned more closely to the price data set. To do that we can use <a href="https://en.wikipedia.org/wiki/Gradient_descent" target="_blank">gradient descent</a> method (other complicated solutions are also avilable, like <a href="https://en.wikipedia.org/wiki/Conjugate_gradient_method" target="_blank">conjugate gradient descent</a> or <a href="https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" target="_blank">BFGS</a> , these are better than simple gradient descent , but complex to implement).<br />
<br />
So for implementing gradient descent we need to find the gradient of function <b>J </b>with respect to <b>t0 </b>and <b>t1 . </b>You can use matlab to find that or find it manually. Following are the results<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnTGcgk5_R2FpmTPWWOaSnz_0p33PjHQvkoIV3B2mj2fi7RmFsjSxgMwx1V6icaqTqzGG5X_sSzVew7X2R1IZCZ8Iz2JSdNjlipxBKCxA5qSocnYntPkXyBi0iwi50_pGa7lGovyh27_Q/s1600/dt0.png" imageanchor="1"></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikv87vNm5mHbfRLE1cNoJyItYViHU1Rl928ioDwTmRj9QLb8TroCT12ILzXTg4A-bQoeZl8_FML_bxct2QbcpFXjsqJsZDcqwGwKaV7KM_rnwgsvpFrte21UElNzlZIux1r_JY6nmFTdc/s1600/dt0.png" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikv87vNm5mHbfRLE1cNoJyItYViHU1Rl928ioDwTmRj9QLb8TroCT12ILzXTg4A-bQoeZl8_FML_bxct2QbcpFXjsqJsZDcqwGwKaV7KM_rnwgsvpFrte21UElNzlZIux1r_JY6nmFTdc/s1600/dt0.png" /></a><br />
<br />
Now apply gradient descent to minimize function J. Below shown the steps to do this in matlab.<br />
<br />
<br />
<blockquote style="text-align: left;">
<span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% X values</span><span style="font-family: "courier new" , "courier" , monospace;">sampleX = [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16];</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% Y values</span><span style="font-family: "courier new" , "courier" , monospace;">sampleY = [100 110 120 122 125 135 112 122 128 129 130 124 117 116 128 132 125];</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% Y predicted using final model.</span><span style="font-family: "courier new" , "courier" , monospace;">resultY = [sampleY ];</span><span style="font-family: "courier new" , "courier" , monospace;">ss = size(sampleY);</span><span style="font-family: "courier new" , "courier" , monospace;">m = ss(2);</span><span style="font-family: "courier new" , "courier" , monospace;">resultC = zeros(ss(2),3);</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">cmap = hsv(1);</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">error = [];</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">theta0 = 50;</span><span style="font-family: "courier new" , "courier" , monospace;">theta1 = 1;</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;"><br /></span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% main iteration loop</span><span style="font-family: "courier new" , "courier" , monospace;">for i = 1:1:10000</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;"><br /></span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% function H</span><span style="font-family: "courier new" , "courier" , monospace;">newSampleY = theta0 + theta1 * sampleX;</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">deviation = sum((newSampleY - sampleY).^2);</span><span style="font-family: "courier new" , "courier" , monospace;">deviation = deviation / (2*ss(2));</span><span style="font-family: "courier new" , "courier" , monospace;">error = [ error ;deviation ];</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">resultY = [newSampleY];</span><span style="font-family: "courier new" , "courier" , monospace;">colorPoints = zeros(m,3);</span><span style="font-family: "courier new" , "courier" , monospace;">colorPoints(1: end,1) = cmap(1,1);</span><span style="font-family: "courier new" , "courier" , monospace;">colorPoints(1: end,2) = cmap(1,2);</span><span style="font-family: "courier new" , "courier" , monospace;">colorPoints(1: end,3) = cmap(1,3);</span><span style="font-family: "courier new" , "courier" , monospace;">%resultC = [resultC; colorPoints];</span><span style="font-family: "courier new" , "courier" , monospace;">resultC = [ colorPoints];</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;"><br /></span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% derivative of J w.r.t t0</span><span style="font-family: "courier new" , "courier" , monospace;">theta0Gradient = sum(newSampleY - sampleY) / m;</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% derivative of J w.r.t t1</span><span style="font-family: "courier new" , "courier" , monospace;">theta1Gradient = sum((newSampleY - sampleY).*sampleX ) / m;</span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;"><br /></span><span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">% applying gradient descent operation to minimize J</span><span style="font-family: "courier new" , "courier" , monospace;">theta0 = theta0 - .01 * theta0Gradient;</span><span style="font-family: "courier new" , "courier" , monospace;">theta1 = theta1 - .01 * theta1Gradient;</span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">end </span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">scatter([sampleX sampleX],[sampleY resultY],[],[ zeros(m,3); resultC]);</span><span style="font-family: "courier new" , "courier" , monospace;">axis([0 50 -100 100]);hold; </span><span style="font-family: "courier new" , "courier" , monospace;"><br /></span><span style="font-family: "courier new" , "courier" , monospace;">fprintf('\ncomputed error values\n');</span><span style="font-family: "courier new" , "courier" , monospace;">error</span></blockquote>
<br />
Below image show the result after running this code. <b><span style="color: #990000;">Red </span></b>circles indicate the points generated using final model, <b>black </b>circles indicates the input data.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLmJr5eoiOF2fiQaiwGLjRPiLxLd2-_PHSbideBvFqqg6gj__yJLm99tUHvAwcLfLU8Jy2aaFooc2IgnNZGkT6do1MmIZIhVB2f0Mp3_xeE8i2vc1IUR9aXC5VQvxVN222CwIvw5x-FcE/s1600/graph.png" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLmJr5eoiOF2fiQaiwGLjRPiLxLd2-_PHSbideBvFqqg6gj__yJLm99tUHvAwcLfLU8Jy2aaFooc2IgnNZGkT6do1MmIZIhVB2f0Mp3_xeE8i2vc1IUR9aXC5VQvxVN222CwIvw5x-FcE/s1600/graph.png" /></a><br />
<br />
Another example showing how we can use this to fit a quadratic curve to input points.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsY-o6uzz7Zd60WHC-fsfS62hhpmRa4XRtpxF4s-B0kTlzWKYT8fn8zM85Ub4OkPIQIqlJUEELhP_e7N6Y7mJXS_ZDgGybIL-77kubvRWir5C89xNDMI4sfyoQZ6yvFaQu4FEOpYhQ-yg/s1600/graph_curve.png" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsY-o6uzz7Zd60WHC-fsfS62hhpmRa4XRtpxF4s-B0kTlzWKYT8fn8zM85Ub4OkPIQIqlJUEELhP_e7N6Y7mJXS_ZDgGybIL-77kubvRWir5C89xNDMI4sfyoQZ6yvFaQu4FEOpYhQ-yg/s1600/graph_curve.png" /></a><br />
<br />
<br />
<br />
<b><br /></b>
<b><br /></b>
<br />
<br />
<br />
<div>
<br /></div>
testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-23389294496219052322013-07-14T00:03:00.000+05:302013-07-14T00:03:57.363+05:30Implicit surfaces and Level SetThings are more complicated in discretized form. Say a line when discretized is not actually a line, Right(remembering the bresenham line algorithm ) ? Same thing goes to circle or any shapes. So for computing the associated properties we need more techniques. Implicit surface helps us to compute such properties.<br />
<br />
Before I explain about implicit surfaces, you tell be what is the gradient of a scalar surface/curve.<br />
Say you define a 3D surface by the equation x*x + y*y + z*z = 9, we can easily see that this surface is nothing but a sphere with radius 3. Right ?<br />
So Q(x,y,z) = x*x + y*y + z*z - 9 = 0.<br />
What is the gradient of Q then ? it represents the normal at any point on this surface , and it is (2x,2y,2z) (not normalized).<br />
<br />
Why i said this was to show you how easy it is compute the gradient of a surface with an explicit equation. We can also easily compute other properties related with that surface like tangent,curvature,etc.<br />
<br />
But what can you do if you don't have such explicit equations. In practical things will be like this.<br />
In Implicit form we can define a shape implicitly. Our shape <b>must be closed and non-self intersecting</b>. With this agreement we can define the shape with following definitions.<br />
<br />
Let P ( { Xi,Yi } ) be our point set which denotes the boundaries of our shape. We can define shape implicitly based on the following conditions.<br />
<br />
<span style="font-family: inherit;">1. For all points in shape boundaries <span style="background-color: white; color: #222222; font-weight: bold;">∅</span><span style="background-color: white; color: #222222;"> (Pi</span><span style="background-color: white; color: #222222;">) = 0</span></span><br />
<span style="font-family: inherit;"><span style="background-color: white; color: #222222;">2. For all other points outside the shape </span><span style="background-color: white; color: #222222;">∅(Pi) must be > 0 </span></span><br />
<span style="font-family: inherit;"><span style="background-color: white; color: #222222;">3. </span><span style="background-color: white; color: #222222;">For all other points inside the shape </span><span style="background-color: white; color: #222222;">∅(Pi) must be < 0 . (Conditions 2,3 can be interchanged though) </span></span><br />
<span style="font-family: inherit;"><span style="background-color: white; color: #222222;"><br /></span></span>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcWgYiPG3CDW6Z6XZGfhfuVCxFuhQKVGz_EvDbczAPVUAsdeM5VK2Dl5fg_n695EmqznVOCE-PKQ0pjfs4fC-3-0iTEQkc3Z6PNNMfJZZizyAo1yYRNCTuzd63MM6lM1HturspNBBL8Pw/s1600/grid.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="247" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcWgYiPG3CDW6Z6XZGfhfuVCxFuhQKVGz_EvDbczAPVUAsdeM5VK2Dl5fg_n695EmqznVOCE-PKQ0pjfs4fC-3-0iTEQkc3Z6PNNMfJZZizyAo1yYRNCTuzd63MM6lM1HturspNBBL8Pw/s320/grid.png" width="320" /></a></div>
<span style="font-family: inherit;">Based on the earlier definitions consider the above picture. Pixel's with green boundary is our shape <span style="font-family: inherit;">where </span></span><span style="background-color: white;"><span style="color: #222222; font-family: inherit;">∅(Pi) will be 0. pixels having red color will have negative value, and rest of the pixels (blue) will have positive value. This is how we define implicit functions for complicated shapes. In the next post I will show you how we can numerically compute the properties of these shapes from this </span><span style="color: #222222;">definitions also will introduce about level sets</span><span style="color: #222222;"><span style="font-family: inherit;">. It is not a big deal( Actually i had </span>intention<span style="font-family: inherit;"> to write more about this, but I lost my mood so stopping now )</span></span></span>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-38908965667788063962013-06-15T22:27:00.000+05:302013-06-17T20:40:33.283+05:30Curvature Flow & Smoothing curvesI am getting addicted to curves. They are the perfect beautiful representation which we can numerically compute. I don't want to express more my feelings towards it which may be boring to you.<br />
<br />
Coming to the topic, curvature flow is a kind of method to modify the curve.<br />
Take any planar non intersecting curves , find the curvature at each point and multiply with it the normal there, then move the curve along that direction. This is the concept. It is analogs to the heat exchange. Heat will eventually spread uni-formally , no matter how you wrap it.<br />
<br />
So take a curve {X(s),Y(s)} and it's curvature and normal , Say {K(s)} and {N(s)}.<br />
Then curvature flow vector is defined as {K(s)*N(s) }.<br />
<br />
Using this technique we can smooth the curve from noise. Eventually this curve will become circular and will vanish. it is possible to know the exact point where it will vanish.<br />
<br />
I just made a quick demo of this with matlab. See the images below<br />
<br />
<b>Original curve</b>.<br />
We can see that some edges are not smooth (think of it like created by noise).These spikes(non-smooth) in edges are not influencing our capability to detect the shape.We humans normally pick up a smooth shape from a contour. Now we want to remove some noise (or say smooth it) using curvature flow.<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTT6IhdHYT5ZYPJobmz47wNdVBiTyEqi20lBa7FA1vOFla0KxKYni-ichRkJGixQ62qBiZV5cl99nuG4vXJKZJE4D-D3l-EPmdPpZpTNE6vQSO1Ciemq-shi4YQSDJCzsjUwfgFakutko/s1600/noisy+data.bmp" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTT6IhdHYT5ZYPJobmz47wNdVBiTyEqi20lBa7FA1vOFla0KxKYni-ichRkJGixQ62qBiZV5cl99nuG4vXJKZJE4D-D3l-EPmdPpZpTNE6vQSO1Ciemq-shi4YQSDJCzsjUwfgFakutko/s1600/noisy+data.bmp" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<b>After 10 iteration</b></div>
<div class="separator" style="clear: both; text-align: left;">
See that curve is more smooth now.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKnHSAHI62HUPivFabFmsz8DmPhlQuv0Xs1jyWvhWmAgEPlYSKcAJ2RNbBZ269PP8dGLleY6LxNh62sSTEeAkaKqJul353GhdmxnqoGe-1oQvkVIrCF3_47nt69kXMul1NLAZpfvb5MBo/s1600/curvature+flow+after+10.bmp" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKnHSAHI62HUPivFabFmsz8DmPhlQuv0Xs1jyWvhWmAgEPlYSKcAJ2RNbBZ269PP8dGLleY6LxNh62sSTEeAkaKqJul353GhdmxnqoGe-1oQvkVIrCF3_47nt69kXMul1NLAZpfvb5MBo/s1600/curvature+flow+after+10.bmp" /></a></div>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b>Curve after 50 Iterations</b><br />
Curve is getting circular. Yeah, it will become circular at one point , because circle is the only one shape with a non-zero uniform curvature.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6amzgF78oMaaosYHkaKzobBhOzI5XyCYngkl6bK-bt-O8T65iS955OkWF860uiRmXhobza9abazwxspOZQUukh1QHdcNcAe1DcDJJNmIbcWTgnRD2FKlFdRSJBtLxoFxsdTahxa4-FeY/s1600/curvature+flow+after+50.bmp" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6amzgF78oMaaosYHkaKzobBhOzI5XyCYngkl6bK-bt-O8T65iS955OkWF860uiRmXhobza9abazwxspOZQUukh1QHdcNcAe1DcDJJNmIbcWTgnRD2FKlFdRSJBtLxoFxsdTahxa4-FeY/s1600/curvature+flow+after+50.bmp" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
This is type of smoothing is also possible with Gaussian filtering along the curve,but with lesser accuracy. This type of technique can also be extended to 3D, Say you are having an object and you want to add a higher layer of layer/cover to it. Rather than just extending the surface along normal , use curvature flow.Then the surface will be more appealing and natural (I Guess).<br />
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com2tag:blogger.com,1999:blog-3996848416074637521.post-35518927916839402122013-05-22T23:37:00.002+05:302013-05-24T18:39:06.637+05:30Simple 2 Dimensional Curve Matching <span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">In my previous post I have explained about curvature in depth. Now to the practical side, I created a simple application which will use these curvature to compare two simple planar curves. In the following video you can see two feature vectors indicates the similarity of curves;</span><br />
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">See the video here.</span><br />
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><b>The angle difference between the feature vectors indicates how similar those shapes are</b>.In the video, you can also see that this <b>matching is invariant to rotation and scale</b>(when shape gets bigger, curvature will becomes lower). Right now the algorithm I used for computing the curvature 'Feature vector' is based on centroid. It needs to be refined further,But the underlying theory is very solid.Also the first impression giving me a very good hope on the concept.</span><br />
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><br /></span>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.blogger.com/video.g?token=AD6v5dwmfxUTj9edN17MawMLNKGL8SpMVTVD_HaItVhVjqL0N4giNxSRs85yu4KFXCePuao9ZfdkDzYOBm2rJMFPFQ' class='b-hbp-video b-uploaded' frameborder='0'></iframe></div>
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><br /></span>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">However I am stopping my work on this concept, I don't have time to refine it. Next my target is 'level set methods' or solving the thin plate spline equation. The second one is duper super hard to fully understand , I already attempted it and lost my mind and motivation.Whenever I take it , suddenly everything becomes complicated, even my life (incidents!). So it is like the book of <a href="http://mummy.wikia.com/wiki/Book_of_Amun-Ra" target="_blank">Amun-ra</a> But after looking it, I knew that i need to improve my 'calculus of variation' skills , and that topic is very nice.The same thing which helps to solve missile guidance problems!.</span><br />
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-11638480949139474902013-05-22T17:58:00.004+05:302013-05-23T09:50:54.286+05:30Curvature: Deriving the formula based on non-length parameter.<span style="font-family: Arial; font-size: 15px; line-height: 1.15; white-space: pre-wrap;">Matching curves is an important operation in computer vision. Several methods are there. But the important thing is how we are defining the curves. </span><span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe"></span><br />
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe">
</span>
<br />
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe"><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">This time i am writing about some concept which uses the curvature to do this matching operation. In some of my previous posts i had written about parameterizing the curve based on length(parameter 's').It is important to understand such concepts which will help us to apply some imagination.</span></span></div>
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe">
</span>
<br />
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe"><span style="vertical-align: baseline;"><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">Curvature 'k' is the magnitude of second derivative of a curve which is parameterized using length </span></span><span style="font-family: Arial;"><span style="font-size: 15.454545021057129px; line-height: 15.454545021057129px; white-space: pre-wrap;">parameter</span></span><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">('s')</span></span></span></span></div>
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe">
</span>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe"><span style="vertical-align: baseline;"><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">In real </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">scenarios</span><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">(live)we will not have the </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">luxury</span><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> of getting curves which follows some strict equations.Most of the cases what we get is some points(</span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">of-course</span><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> again corrupted by some noise).</span></span></span></span></div>
<span id="docs-internal-guid-4202adc2-c20d-75d3-d34c-2f7db7d89dfe">
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="vertical-align: baseline;"><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">We need to use a numeric approximation here to find the derivatives. That is simple,the hardest part is making a list with </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">ordered</span> <span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">point</span><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> pairs in the correct order which will closely matches the property of the original curve</span></span></span></div>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="vertical-align: baseline;"><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">Once we have such a list, it is possible to use curvature for matching. Now you may think like curvature is the magnitude of second derivative based on 's' parameter. So do we need to again parametrize the curve to 's' ? (i had this thought ). No need , we can find a </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">curvature</span><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> based on non-length parameter too.</span></span></span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Here it is.</span></div>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="vertical-align: baseline;"><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">Say our curve is r(s) = { x(s),y(s) }, s is from 0 to length </span></span></span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Now we need to find dr/dt. ( 't' is non-s parameter )</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">dr(s)/dt = (dr/ds) * (ds/dt) [ using chain rule) ]</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"> = t * v (lets call (dr/ds) as tangent (t vector, not same as parameter 't' which is scalar) w.r to s, and ds/dt as 'v' which will tell how wast length is changing with respect to 't']</span></div>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">Now we need to find d^2r(s)/dt^2</span></span></div>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = d(t)/dt * v + dv/dt * t</span></span></div>
<div dir="ltr" style="margin-bottom: 10pt; margin-top: 0pt;">
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = d(dr/ds)/ds * (ds/dt) * v + (dv/dt) * t [again using chain rule of diff., first differentiate with s, because r is a function of 's' , then differentiate 's' w.r to 't']</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = d(dr/ds)/ds * v * v + (dv/dt) * t</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = dt/ds * v^2 + (dv/dt) * t</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">Here dt/ds is actually the second derivative of 'r' with respect to parameter 's'. This quantity can be written as k*n,where k is a constant and n is a unit normal vector. So the equation will become</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = k*n * v^2 + (dv/dt) * t</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">Now take cross product between dr(s)/dt , d^2r(s)/dt^2</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">dr(s)/dt X d^2r(s)/dt^2 = (t*v) X (k*n*v^2 + (dv/dt) *t )</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = (t*v) X (k*n*v^2) [because tXt is zero ]</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = t X (k*n*v^3) [ in this only t, and n are vectors.It is very much clear.]</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> = (k*t*v^3) X (n)</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"></span><br />
<span style="font-family: Arial;"><b><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">So dr(s)/dt X d^2r(s)/dt^2 =</span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> kv^3t x n ---------------- (1)</span></b></span><br />
<span style="font-family: Arial;"><br /></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">vector t in the previous equation (1) is dr/ds, tangent vector of curve which is parameterized over 's' and is always unit length. </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">so that means we can find 't' just by normalizing the vector 't'.</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">t = <dx(t)/dt,dy(t)/dt,0> / Norm[ <dx(t)/dt,dy(t)/dt,0> ]</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">the vectors 't' and 'n' lies in the x,y plane and also perpendicular. so take a vector 'z' which is also </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">perpendicular to the x-y plane and its value is (0,0,1). so these three vectors (t,n,e) form a 3 dimensional coordinate system. </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">By using normal cross product logic we can interpret vector 'n' as cross product between e and t.</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><b>n = e x t </b></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">lets call dr(s)/dt simply as dr</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">lets call d^r(s)/dt^2 simply as drr </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">so </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">dr x drr = kv^3t X (e x t )</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">=(dr x drr)/ v^3 = k* t x (e x t )</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">=(dr x drr)/ v^3 = k*( e(t.t) - t(t.e))</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">=(dr x drr)/ v^3 = k*( e(t.t) - t(t.e))</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">=(dr x drr)/ v^3 = k*( e(t.t) - t(0))</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">=(dr x drr)/ v^3 = ke</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">k = (e. (dr x drr)) / v^3</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><b>k = (<0,0,1> . (dr x drr)) / v^3</b></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">Now lets find dr x drr</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">if we know the curve 'r' , we can easily find dr and drr. first parameterize curve to 't' , mostly all curve's </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">natural parameterization will be t which is non-arc length parameter. Say you are drawing some a curve with mouse, then points will be placed on the order you place it right ? it may not be possible for you to place points with equal interval considering the total length of curve.</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">so </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> dr = < dx(t)/dt ,dy(t)/dt ,0 ></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"> drr = < d^2x(t)/dt^2 , d^2y(t)/dt^2 ,0 ></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><b>dr X drr = <0,0,(dx(t)/dt) * d^2y(t)/dt^2 - dy(t)/dt * d^2x(t)/dt^2> = <0,0,dx*dyy - dy*dxx></b></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">so k = (<0,0,1>. <0,0,dx*dyy - dy*dxx>) / v^3</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><b> k = (dx*dyy - dy*dxx>) / v^3</b></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">we need to get ride of v also. 'v' is ds/dt . </span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">what is the value of 's' , it is a function of length</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">s = Integrate [ Sqrt[ |dr/dt| ] ] over the entire curve. Differentiating it again with respect to t , we get </span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">ds/dt = Sqrt[ |dr/dt| ] = v</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">k = (dx*dyy - dy*dxx>) / Sqrt[ |dr/dt| ] ^3</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><b><span style="color: #990000;">k = (dx*dyy - dy*dxx>) / (dx^2 + dy^2) ^(3/2)</span></b></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">This is the final equation for finding curvature of plane curve which is not parameterized on arc length parameter.</span><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">This k is invariant to rotation, only problem lies in how efficiently we can parameterize the curve which follows the properties which we used to derive this 'k'.</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">see the images which shows the original curve, its curvature('k') plot, rotated image and its curvature plot. We can see that the curvature remains same.</span></span><br />
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span><span style="font-family: Arial;"><span style="font-size: large; line-height: 17px; white-space: pre-wrap;">original curve</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<span style="font-family: Arial;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYMOGR5xdfLolNatbq8S6HIX-z47wm_q-BJR7FIxRFDp0pvUlqUjwP1K51HUnk5NFPuKWM4IYVmlFSFEO0CeqdE5_Td9rwNw5clZNqfEkcS-0J8U3b2_baW37hQkpAKlylcMpANCe1njI/s1600/original+curve.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYMOGR5xdfLolNatbq8S6HIX-z47wm_q-BJR7FIxRFDp0pvUlqUjwP1K51HUnk5NFPuKWM4IYVmlFSFEO0CeqdE5_Td9rwNw5clZNqfEkcS-0J8U3b2_baW37hQkpAKlylcMpANCe1njI/s1600/original+curve.png" /></a></span></div>
<span style="font-size: large;">curvature plot of original curve</span><br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="font-family: Arial;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxhLcPiLG9tH-9RqtnBLVy_IzpvOYq1VqtjQ20hBci4WDoRjoi7Wo05XmlTkf966DflpeVUTDE0ZoZGcprHzlZkatjyPO1kudMZoBJip-JTqnfwolUQDVi2DRP7cuyhJXNWchKMMV4yNY/s1600/rotated+image+-+curvature.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxhLcPiLG9tH-9RqtnBLVy_IzpvOYq1VqtjQ20hBci4WDoRjoi7Wo05XmlTkf966DflpeVUTDE0ZoZGcprHzlZkatjyPO1kudMZoBJip-JTqnfwolUQDVi2DRP7cuyhJXNWchKMMV4yNY/s1600/rotated+image+-+curvature.png" /></a></span></div>
<div class="separator" style="clear: both; text-align: left;">
<span style="font-size: large;">Rotated curve</span></div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjm0eXjgtvreQqSZ4bP1BVmG76MpxAQ8DAM39k0RSZ24124Cpzl0OFuVd0w6AMkPlM0GkPKJJxSKKrKj1Up2JWqyfloTO9jUfC_2-EOcsgBrBHlP2ww46otIFtRb8OOIVn6MV_aA4aVEls/s1600/rotate+image.png" imageanchor="1" style="font-family: Arial; margin-left: 1em; margin-right: 1em; text-align: center;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjm0eXjgtvreQqSZ4bP1BVmG76MpxAQ8DAM39k0RSZ24124Cpzl0OFuVd0w6AMkPlM0GkPKJJxSKKrKj1Up2JWqyfloTO9jUfC_2-EOcsgBrBHlP2ww46otIFtRb8OOIVn6MV_aA4aVEls/s1600/rotate+image.png" /></a><br />
rotated curve's curvature plot<br />
<div class="separator" style="clear: both; text-align: center;">
<span style="font-family: Arial;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQy55WEIG1UKwne4OJeRi4xcbpdCe8OnT0LmLJe7AZn9oHNF-gHTR5w0xL3RT3locDAxBw3J0bp0CmO6HXa1CYF1oiaWRriqP2UMYwh-1autad5ZE0-d3i4bCf2CiascwodWB0AacJk_g/s1600/curvature+-+plot+-+original.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQy55WEIG1UKwne4OJeRi4xcbpdCe8OnT0LmLJe7AZn9oHNF-gHTR5w0xL3RT3locDAxBw3J0bp0CmO6HXa1CYF1oiaWRriqP2UMYwh-1autad5ZE0-d3i4bCf2CiascwodWB0AacJk_g/s1600/curvature+-+plot+-+original.png" /></a></span></div>
<span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;"><br /></span></span><span style="font-family: Arial;"><span style="font-size: 15px; line-height: 17px; white-space: pre-wrap;">From the figures we can see that curvature remains same. we can use this feature for matching planar curves. I will post some video of that in next post. </span></span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 10pt; margin-top: 0pt;">
<br /></div>
<div>
<span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
</span>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-50076461983029868402013-04-04T01:21:00.002+05:302013-05-23T09:50:54.297+05:30Wiener Filter + Inverse Filter, Contd.In the last post i derived the formula for wiener filter. I am not getting enough time to write something here. This night i decided to write something. If you carefully examine the wiener filter formula it can be seen that when the K is zero ( that is no noise),it act just an inverse filter.<br />
This means we can just divide the Fourier transform of the input signal(degraded) with the Fourier transform of the degrade function. This will produce the original data. You may be wondering how this works. It is based on convolution theorem.<br />
<br />
In my pc mathematica stopped working. So i am switching to matlab from now on<br />
<br />
Following mat lab snippet proves that convolution in spatial domain and frequency domain is same<br />
<br />
<span style="color: blue;">%% in this example convolution signal is not centered ( so the source)</span><br />
<span style="color: blue;">%% by this way we can avoid the one shifting(ifftshift) at the end.</span><br />
<br />
<span style="color: blue;">data1 = [1,2,3,2,1,0,0];</span><br />
<span style="color: blue;">kernel = [1,1,1];</span><br />
<span style="color: blue;">kernel_padded = [1,1,1,0,0,0,0];</span><br />
<span style="color: blue;">'convolution spatial'</span><br />
<span style="color: blue;">conv(data1,kernel,'valid')</span><br />
<span style="color: blue;">d = fft(data1) .* fft(kernel_padded);</span><br />
<span style="color: blue;">'fourier'</span><br />
<span style="color: blue;">ifft(d)</span><br />
<div>
<br /></div>
<br />
When you run it this will produce the result 1 3 6 7 6 3 1. (conv function will out two more zeros, but it is not a part of input data)<br />
<br />
Using this idea inverse filter works. Since inverse filter uses a division problem can happen when the denominator is zero or say too high. because of this it is not stable as itself also with noise.<br />
<br />
Here is the results and code<br />
<br />
<span style="color: blue;">a = imread('f:\\ip\\imtests\\exotic.jpg');</span><br />
<span style="color: blue;">d = rgb2gray(a);</span><br />
<span style="color: blue;">degrade = [.1 .1 .1;.1 .5 .1;.1 .1 .1];</span><br />
<span style="color: blue;">dim = conv2(d,degrade,'valid');</span><br />
<span style="color: blue;">figure('Name','degraded image with some filter')</span><br />
<span style="color: blue;">imshow(dim,[0,255])</span><br />
<span style="color: blue;"><br /></span>
<span style="color: blue;">img_size = size(d) ;</span><br />
<span style="color: blue;">img_size = size(dim); </span><br />
<span style="color: blue;">conv_mat = zeros(img_size(1),img_size(2));</span><br />
<span style="color: blue;"><br /></span>
<span style="color: blue;">% create conv matrix for inverse.</span><br />
<span style="color: blue;">pw = floor(img_size(1))-3</span><br />
<span style="color: blue;">ph = floor(img_size(2))-3</span><br />
<span style="color: blue;">conv_mat = padarray(degrade,[pw,ph],'post');</span><br />
<span style="color: blue;"><br /></span>
<span style="color: blue;">fo = fft2(dim);</span><br />
<span style="color: blue;">fc = fft2(conv_mat);</span><br />
<span style="color: blue;">% the final division.</span><br />
<span style="color: blue;">myimg = fo ./ (fc )</span><br />
<span style="color: blue;"><br /></span>
<span style="color: blue;">corrected = ifft2(myimg);</span><br />
<span style="color: blue;">figure('Name','corrected with inverse filter')</span><br />
<span style="color: blue;">imshow(real(corrected),[0 255])</span><br />
<div>
<br /></div>
<div>
<b>Oringal Image</b></div>
<div>
<br /></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_hFBUUbcVA9jQc-PSfYjFn3dXaE4gnQI2CCU8Wlh-x37ZjwuJlEm5xDmIpFhLFNbl9y_miUBFNH9FO83McwcBuF3_4VgWhE9ZmFV4s28rkeVU2h6KpTADVGEVpLePnTdUcJ9pKYiK_A0/s1600/fruit_d.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_hFBUUbcVA9jQc-PSfYjFn3dXaE4gnQI2CCU8Wlh-x37ZjwuJlEm5xDmIpFhLFNbl9y_miUBFNH9FO83McwcBuF3_4VgWhE9ZmFV4s28rkeVU2h6KpTADVGEVpLePnTdUcJ9pKYiK_A0/s1600/fruit_d.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<b><br /></b></div>
<div class="separator" style="clear: both; text-align: left;">
<b>Corrected with Inverse</b></div>
<b><br /></b>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYX_zKf_SC1crSa9-0Vea_CgRoY3oz4PIheMf0z4FM9WMVlhXwl75p-ILosjWJSrj3V7RrD8i9OnXJFXT_T1MA_vJ5Y8ev6B3gKLUcRMVf2lPyQaP9aDaUwn4mEEuufiGe-a9C-5H-0hs/s1600/fruit_c.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYX_zKf_SC1crSa9-0Vea_CgRoY3oz4PIheMf0z4FM9WMVlhXwl75p-ILosjWJSrj3V7RrD8i9OnXJFXT_T1MA_vJ5Y8ev6B3gKLUcRMVf2lPyQaP9aDaUwn4mEEuufiGe-a9C-5H-0hs/s1600/fruit_c.png" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
Don't expect this kind of correction all cases , because of that division things can go totally wrong . So one idea is to add some constant with denominator before division and play with it until you find some satisfactory results Or you need to check it against zero or non-numeric value.</div>
<div class="separator" style="clear: both; text-align: left;">
Ok its time for me to stop. I just made this because of me :) . I was worried about not writing anything for sometime. That's why this quick post. More interesting this are coming(to my mind)</div>
testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com1tag:blogger.com,1999:blog-3996848416074637521.post-41127961719790616802013-03-08T02:03:00.003+05:302013-05-23T09:50:54.292+05:30Wiener Deconvolution: Deriving the final formula<br />
Recently i watched a video which talks about noise and filtering.That why i am posting this.After searching the same in wiki, i didn't see a detailed derivation of the formula. so I thought to write this and post.<br />
<br />
Wiener deconvolution is a frequency domain technique which helps to remove the noise if we know the degradation function(H(t)) in advance. The degradation function degrades the image quality. It can be blurring like Gaussian blur or it can be motion blur.<br />
<br />
X(x,y) -> Passes through degradation function -> Some noise gets added here(N) -> our final signal Y(x,y)<br />
<br />
If we multiply the Y with Wiener filter then it will provide an approximation of X. Lets call this approximation as X$ .Now am going to write down the full derivation. a part of this is available in wiki. But those who are not remembering complex number maths may find it difficult.<br />
<br />
Mean square error between approximation and original data is = E | X(x,y) - X$(x,y) | ^2<br />
<br />
but we know X$ is can be obtained by G(x,y) * Y(x,y) [ * is convolution operator ]<br />
= E( | X(x,y) - G(x,y) * Y(x,y) |^2)<br />
But if convert all to frequency domain convolution becomes multiplication, ie a(t)*b(t) = a(f)b(f)<br />
Also we know Y is X * H + N<br />
= E(| X - G ( XH + N)) |^2)<br />
= E(| X - GXH - GN) |^2)<br />
= E(| (1 - G H)X - GN) |^2)<br />
<br />
if A and B are two complex numbers | A B |^2 = (A B)(AB)* , here * is complex conjugate.<br />
<br />
= E( ((1-GH)X - GN)((1-GH)X - GN)* )<br />
= E( ((1-GH)X - GN)((1-G*H*)X* - G*N*)) , here all * means complex conjugate<br />
<br />
Expanding this is a painful thing. but i am not giving up. So are you ?<br />
<br />
= E( ((1-GH)X(1-GH)* XX* - (1-GH)XG*N* - GN(1-GH)*X* + GNG*N* )<br />
= ( (1-GH)(1-GH)* E{|X|^2} - (1-GH)G* E{XN*} - G(1-GH)* E{NX*} + GG* E{|N|^2}<br />
wooha,<br />
Lets assume noise and input signal has no relation,That why it is noise. So we can just ignore the terms E{XN*} ,E{NX*}.I think this is because at a particular frequency we can't find any relation between input data and noise. So the probability is null here. That why taking E( expectation) which sums the probability of values. here since we can't find any probability we can assume it 0.<br />
<br />
We can denote S(f) = E{|X|^2} , it is the power spectrum of the complex values of the input data<br />
We can denote N(f) = E{|N|^2} , it is the power spectrum of the complex values of the noise data<br />
<br />
so final equation becomes<br />
<br />
minError(f) = (1-GH)(1-GH)* S + GG*N<br />
Now we need to find the minimum error which we can obtain for G. So following the basic calculus (like how we will find the min value of a function ) . careful about G* ,it is not G. So we can treat that as constant.<br />
<br />
d(minError(f)/dG = -H(1-GH)*S + G*N = 0 ,<br />
Now we need to find G from this. we will find it in a minute.<br />
<br />
<br />
That is G*N - H[1-GH]*S = 0<br />
<br />
G*N = HS[1-GH]*<br />
G*N = HS[1-G*H*]<br />
G*N = S[H-G*HH*]<br />
G*N = S[H-G*|H|^2 ]<br />
G*N = SH-SG*|H|^2 ]<br />
G*N = (G*) [ (1/G*)SH-S|H|^2 ]<br />
N = [ (1/G*)SH - S|H|^2 ]<br />
N + S|H|^2 = SH/G*<br />
G*/SH = 1/ (N+ S|H|^2 )<br />
G* = SH / ( N+ S HH* ). Take out s<br />
G* = SH / S( N/S+ HH* )<br />
<div>
N/S is noise to signal ratio, We can replace it with a constant K</div>
<br />
<br />
G* = H / (K+ HH* )<br />
G = H*/ (K+H*H), H*H is |H|^2|<br />
G = H*/ (K+|H|^2)<br />
<br />
Yes we reached the final answer , G = H*/(K+|H|^2).<br />
if you know H, then you can find G, Then just multiply this with Fourier transformed input data. you will get a better picture. Thus you can remove some noise from the input data. In next post i will try to post some samples after applying G or wiener filter. Be ready for it.testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com2tag:blogger.com,1999:blog-3996848416074637521.post-4516987614836399382013-02-24T21:49:00.003+05:302013-05-23T09:50:54.294+05:30Histogram Equalization : A simple technique for improving low contrast imagesI have been busy. Not getting much time to give enough attention to this. I am really worried about this and this makes me unhappy. But life must goes on. I can do what i want but i am not able to do.. It is an interesting thought. I am sure many of us still have this.(just had a wine)<br />
<br />
What is histogram , it is a frequency showing some information in image. Due to some factors based on the equipment or lighting or whatever it is possible sometimes taken image will contain colors that uses near by gray values. That is is the image's gray levels are not really stretched to required level.<br />
<br />
See some images <a href="https://www.google.com/search?q=low+contrast+images&hl=ml&safe=off&biw=1138&bih=499&tbm=isch&tbo=u&source=univ&sa=X&ei=aDgqUY-HD8SYhQfs6YHIBA&ved=0CCoQsAQ" target="_blank">here</a><br />
These are images taken on low light or artificially generated. if you examine this these uses intensities that are around near by spectrum.That is why our eye is not able to perceive the amount of detail we want to interpret. Histogram equalization is a very simple technique to stretch out this contrast by using a cumulative distributive function.<br />
<br />
This CDF function is very simple, it means for the pixel with highest value it assigns a probability of 1, because it is cumulative That is for the brightest pixel value( say 255) it sums probabilities of all pixels from 0 to 255 and it must be 1 it will be (for other pixel values it sum ups probabilities up to that pixel's value). So our CDF function is a monotonically increasing function.<br />
<br />
I am attaching the mathematica code and results. so i don't have to explain.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">yimage = Import["f:\\imtests\\lowContrast1.jpg"];</span><br />
<span style="font-family: Courier New, Courier, monospace;">grayImg = ColorConvert[myimage, "GrayScale"];</span><br />
<span style="font-family: Courier New, Courier, monospace;">mydata = ImageData[grayImg, "byte"];</span><br />
<span style="font-family: Courier New, Courier, monospace;">temp = ImageDimensions[grayImg];</span><br />
<span style="font-family: Courier New, Courier, monospace;">width = temp[[1]];</span><br />
<span style="font-family: Courier New, Courier, monospace;">height = temp[[2]];</span><br />
<span style="font-family: Courier New, Courier, monospace;">numberOfPixels = width*height;</span><br />
<span style="font-family: Courier New, Courier, monospace;">histo = Array[0 &, 256];</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(* compute histogram *)</span><br />
<span style="font-family: Courier New, Courier, monospace;">m = mydata[[2]][[138]];</span><br />
<span style="font-family: Courier New, Courier, monospace;">For[ i = 1 , i <= height, i++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> For[ j = 1 , j <= width, j++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> m = mydata[[i]][[j]];</span><br />
<span style="font-family: Courier New, Courier, monospace;"> m = m + 1;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> histo[[m]] ++;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(* create cummlative distributive function to map pixels *)</span><br />
<span style="font-family: Courier New, Courier, monospace;">cdf = Array[0 &, 256];</span><br />
<span style="font-family: Courier New, Courier, monospace;">For[ i = 1, i <= 256, i++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> sum = 0.0;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> For[ j = 1, j <= i, j++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> </span><br />
<span style="font-family: Courier New, Courier, monospace;"> sum = sum + histo[[j]] / numberOfPixels;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;"> sum = sum * 255;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> cdf[[i]] = sum;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(* plot cdf *)</span><br />
<span style="font-family: Courier New, Courier, monospace;">ListLinePlot[cdf]</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(* equalize histogram *)</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">orignalData = mydata;</span><br />
<span style="font-family: Courier New, Courier, monospace;">(* change pixels in original image based on cdf function *)</span><br />
<span style="font-family: Courier New, Courier, monospace;">For[ i = 1 , i <= height, i++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> For[ j = 1 , j <= width, j++,</span><br />
<span style="font-family: Courier New, Courier, monospace;"> m = mydata[[i]][[j]] + 1;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> mydata[[i]][[j]] = cdf[[m]]</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;"> ];</span><br />
<span style="font-family: Courier New, Courier, monospace;">Image[orignalData, "byte"]</span><br />
<span style="font-family: Courier New, Courier, monospace;">Image[mydata, "byte"]</span><br />
<br />
<br />
<b>Outputs</b><br />
<br />
<b>CDF function</b><br />
<b><br /></b>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkCOKx4rJ82rChw-mBbG3rHtmxcRxQg4WvkwyNHNBvIfyCTcFIxno3Tw4lknodphyphenhyphenMGLEzy70hyM8Vz4Z1ezAPxnsK06pDC0cL3mkILs9sjkEvN85ojsweR2v7rOlSSeMjaODC720vLQU/s1600/cdf.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="195" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkCOKx4rJ82rChw-mBbG3rHtmxcRxQg4WvkwyNHNBvIfyCTcFIxno3Tw4lknodphyphenhyphenMGLEzy70hyM8Vz4Z1ezAPxnsK06pDC0cL3mkILs9sjkEvN85ojsweR2v7rOlSSeMjaODC720vLQU/s320/cdf.png" width="320" /></a></div>
<b><br /></b>
<b><br /></b>
<b>Original image</b><br />
<b><br /></b>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgF-_HEorz-OcwCfBlaklOTIAyRw-xTK5bwdmi4yahQsQ8U1KotLpxlK0KmS91hteW-Q_RATsrIdR64lQClMTM6Sgu4pmEhct2E9XkxX03bV8hfYiJabeeUgI6fkyVME9603py7HNhrTLg/s1600/unequal.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgF-_HEorz-OcwCfBlaklOTIAyRw-xTK5bwdmi4yahQsQ8U1KotLpxlK0KmS91hteW-Q_RATsrIdR64lQClMTM6Sgu4pmEhct2E9XkxX03bV8hfYiJabeeUgI6fkyVME9603py7HNhrTLg/s400/unequal.png" width="400" /></a></div>
<b><br /></b>
<b><br /></b>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<b><br /></b>
<b>Output image</b><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSRzd9qLZfeU-DFrVnIwKwCatA2hcYC7ecSX7NMFQDVpXDx5dcq7JNuaJCyEbO6q4JVWKtZEHYoWiDqmiNdQDAz6LwQr5RBjpNy4hBiOqKno7FcCV3s4WC9HuwV06ljWL2c9bwVh2x9fo/s1600/equlized.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgSRzd9qLZfeU-DFrVnIwKwCatA2hcYC7ecSX7NMFQDVpXDx5dcq7JNuaJCyEbO6q4JVWKtZEHYoWiDqmiNdQDAz6LwQr5RBjpNy4hBiOqKno7FcCV3s4WC9HuwV06ljWL2c9bwVh2x9fo/s400/equlized.png" width="400" /></a></div>
<b><br /></b>
<b><br /></b>
See how good is the equalized image. but do not expect Histogram Equalization to perform this in all conditions. In general It is good for x-ray images. One other problem is it will also amplify the noise. So it better to remove the noise before passing to this.testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com3tag:blogger.com,1999:blog-3996848416074637521.post-29138585261527614452012-12-17T20:59:00.001+05:302012-12-18T17:14:13.121+05:30Image Compression using DCT (Discrete Cosine Transform) It has been a while , so I decided to write something from memory to keep this blog alive. Currently I am stuck with some differential equations,i really want to solve that by hand. The more i dig, it becomes more complicated.<br />
<br />
DCT aka Discrete Cosine Transform is similar to Fourier transform but uses only Cosine functions.<br />
Its output is just scalar values , not complex numbers as in Discrete Fourier Transform. In image processing point of view it can be used to compress data. Jpeg format uses this technique to compress data. Besides this you can use this property to any field , where you want to get only some influencing data out of your sample.<br />
<br />
There exists different kind of kernel functions for DCT. Out of which common form is shown below.<br />
<img alt="X_k =
\sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) k \right] \quad \quad k = 0, \dots, N-1." src="http://upload.wikimedia.org/math/9/b/9/9b912066d54e929387a28251790b9c4e.png" /><br />
<br />
I copied this from wiki. If you carefully examine you can visualize this as projecting your data on the cosine.<br />
<br />
Let us now apply DCT over an array of numbers<br />
result = FourierDCT[{1, 10, 2, 3, 4, 2, 5, 7, 2, 10, 10, 11, 2}]<br />
{19.1372, -3.7222, 1.37076, 2.10949, -2.33856, 2.01418, -4.42612, 0.769566, -2.33272, -3.44945, -3.3978, 1.07119, -2.33659}<br />
<br />
This is the result , now lets take only first 10 from result array. That is .<br />
len = Length[result]; // assign length (13) to variable len.<br />
compressed = Take[result, 10]<br />
<br />
{19.1372, -3.7222, 1.37076, 2.10949, -2.33856, 2.01418, -4.42612, 0.769566, -2.33272, -3.44945}<br />
<br />
Now lets take Inverse DCT of this compressed data which is expected to give our valuable original data back. Note original array 'result' contained 13 numbers So we need to fill the remaining items with 0's.<br />
<br />
FourierDCT[PadRight[compressed, len], 3];<br />
This will output as below.<br />
{1.682, 8.26, 4.01, 1.549, 4.43, 2.42, 4.41, 6.876, 3.40, 7.369, 13.12, 8.47, 2.96}<br />
Note the similarity with original data , We just did a simple compression on input data and recovered successfully. This is a lossy compression technique. Applying this on image will not reduce the overall quality of image. I mean it is still possible to understand the original image.<br />
<br />
Let us now apply this example on an image. This is our original image, Did you able to recognize him? if you are a German you must. He is the prince of mathematicians.<br />
<br />
This image's dimensions is {220,282} and GrayScale.<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibrwkFbuuPvhUfQKLbR1pckWkWdzQfDqIFJ0xo7O8Kmqwfv0GG46hxVMPrf_1RA7rsfPLW_wzowIflnMxLawEgCK_Q2WGhPCfDF2sDLO_2L3WDq6WOqFsEKmCvNwa4GCSP04HJ7lHZiV0/s1600/original.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibrwkFbuuPvhUfQKLbR1pckWkWdzQfDqIFJ0xo7O8Kmqwfv0GG46hxVMPrf_1RA7rsfPLW_wzowIflnMxLawEgCK_Q2WGhPCfDF2sDLO_2L3WDq6WOqFsEKmCvNwa4GCSP04HJ7lHZiV0/s1600/original.png" /></a></div>
<br />
Lets now take only first 100 rows from this image and compress it<br />
<br />
<br />
dctResult = FourierDCT[ImageData[ image, "Byte"]];<br />
Length[dctResult];<br />
// Here we are only taking first 100 rows from image , that is we are compressing it<br />
compressed = Take[dctResult, {1, 100}];<br />
<br />
Now let us recreate this compressed data again , and see how it looks like<br />
padded = PadRight[compressed, {282, 220}];<br />
resImage = FourierDCT[padded, 3];<br />
Image[resImage, "byte"]<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvmCECTg0A0YTXeDtAd-rMAj-ggnRCGJMtvvnLF3IKhPfl6D0CQXYAwaA_xLYCG5wAX7rqlZVSMVT16yvsu9TJJ6alX561bMhYCgsdK0aspQbYPo3IwAomYSziAbd5uKxO98zv0ukOj5M/s1600/dct+with+100+rows.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvmCECTg0A0YTXeDtAd-rMAj-ggnRCGJMtvvnLF3IKhPfl6D0CQXYAwaA_xLYCG5wAX7rqlZVSMVT16yvsu9TJJ6alX561bMhYCgsdK0aspQbYPo3IwAomYSziAbd5uKxO98zv0ukOj5M/s1600/dct+with+100+rows.png" /></a></div>
<br />
It is not that bad, still you can recognize him.<br />
How about taking 200 rows from the original image. See the output below . It is actually good. We just saved (282-200) * 220 bytes by this simple compression. (282 is original image height, 220 is width)<br />
<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnoX-K1kgAL3ZrXp5F7YBG1c4hTndp5BFofAs_qOIkuzbrcITY6HftK4lP1dT_ZVTVgv3lJmNdhOY8h98i9Ov8iw6wFQ_ET_Q-kNrA5e46OjAWPKduWfrU7RF8AmxloqlNRDX18yNtct4/s1600/dct+with+200+rows.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnoX-K1kgAL3ZrXp5F7YBG1c4hTndp5BFofAs_qOIkuzbrcITY6HftK4lP1dT_ZVTVgv3lJmNdhOY8h98i9Ov8iw6wFQ_ET_Q-kNrA5e46OjAWPKduWfrU7RF8AmxloqlNRDX18yNtct4/s1600/dct+with+200+rows.png" /></a></div>
<br />
I used mathematica program here. Hopes still you could get the idea.<br />
Now again , I am asking , Did you recognize this genius ? if not he is Carl Friedrich Gauss, the Legend.testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-37641566310275843482012-10-24T10:47:00.001+05:302012-10-24T10:51:36.983+05:303D Face creation in AndroidBefore 3 weeks one thought came to my mind, like for creating a 3D surface/object for face image using Opengl ES- Android. Recently I got some time to implement that.<br />
<br />
The the basic idea is like this. Create a mesh surface and texture map it with the image of the face which you want on it. Then provide/implement some tools to bevel up/down on these mesh preserving the smoothness of the surface. I don't want to mention too much details here, because i don't think it contains enough theories which needs explanation.<br />
<br />
See the video below( taken with a web cam). May not have enough clarity. I implemented this app in Java only and it took almost 6 hours. After creating the 3D face object ,App will allow user to export it as OBJ format. But that part needs to be done and i am lazy. So Ii stopped further implementation :)<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.blogger.com/video.g?token=AD6v5dxhCItNEbBybWcIS7Ag0BwmWM_zHkeBCKa64UNR6gzZ8nsaGWLYkK1wUx1UOgtW_1Ve6IQm6TXpdyQ2r1X2ng' class='b-hbp-video b-uploaded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Is anybody interested in the code? ;). </div>
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com2tag:blogger.com,1999:blog-3996848416074637521.post-80334556955415825782012-08-15T22:30:00.000+05:302012-08-15T22:30:38.729+05:30Bending Energy Continued - Finding K<br />
In the previous post I showed how to find F'(s) of a a curve F(t) = <X(t),Y(t),Z(t)><br />
<br />
Now according to the definition of bending energy , it is the integrated sum of squares of curvature over length of the curve. That is we need to find the curvature K(s). It is always like this , Just getting better and better! .<br />
<br />
Curvature is the rate of change magnitude of Unit tangent vector with respect to curve length<br />
That is , it is<br />
<br />
K(s) = || dF'(t) / ds ||<br />
<br />
Lets find dF'(t) / ds<br />
<br />
This is (dF'(t)/ dt) * (dt/ ds) using chain rule of diff.<br />
<br />
= || dF'(t) / dt ||<br />
-----------<br />
|| ds/ dt || we know ds/dt = || F'(t) || from previous post. and dF'(t)/dt is F''(t) .<br />
<br />
K(t) = || F''(t) || / || F'(t) ||<br />
<br />
we calculated the value of K(t). For curves like circle , K(t) is same everywhere ,so just we can remove parameter t for circle. Also for circle there is exists an easier fomula : K = 1 / radius.<br />
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-91054607900151627662012-08-12T23:04:00.000+05:302012-08-12T23:04:00.659+05:30Bending Energy & Parameterization of Curve over length<br />
What is bending Energy ? The precise definition is "it is the sum of squares of curvature of the curve function parameterized over curve length". Bending energy gives the energy stored in the curve. We know any bented objects will store some energy. Bending energy formulation helps to find a value proportional to the energy stored in the curve. For a straight line
bending energy is Zero.<br />
<br />
Before look into it we need to understand how we can parametrize curve over length<br />
<br />
The tricky part is how we can parameterize over curve length.<br />
<br />
Consider a vector valued function F(t) = < X(t),Y(t),Z(t) > , t is the parameter , ranges between some values.<br />
<br />
F'(t) can be found easily by applying partial differentiation on F with respect to 't' .<br />
<br />
Lets now find the length (length function) of this curve<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIv0e_Gv3E7ZrZHaIl5IsKpiZd6QpAxkLmGjmDaARrgz_UonrILdrmKfAmUx18Ua4gTjEXPpyOieZIP2rBRskMZ2qgZfzScDspXjbauSnUtuFYbA7GGt2k7AbXusf5emCavv1UiJ5xUYs/s1600/curve+length.JPG" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIv0e_Gv3E7ZrZHaIl5IsKpiZd6QpAxkLmGjmDaARrgz_UonrILdrmKfAmUx18Ua4gTjEXPpyOieZIP2rBRskMZ2qgZfzScDspXjbauSnUtuFYbA7GGt2k7AbXusf5emCavv1UiJ5xUYs/s1600/curve+length.JPG" /></a></div>
<br />
<br />
<br />
<br />
<br />
it has been shown by <span style="background-color: #ddeeff; font-family: sans-serif; font-size: 11.199999809265137px; line-height: 17.280000686645508px;"><a href="http://homepage.smc.edu/kennedy_john/ArcLengthParametrization.PDF" target="_blank">Kennedy, John (2011) in his paper</a>, </span>how to derive expression for F'(s)<br />
<br />
Differentiating this with respect to s , we will get<br />
<br />
1 = || F'(s) || (of-course s is based on t)<br />
<br />
That means after changing the parameter from t to s(length param) the length of F'(s) is getting 1. It is very interesting concept, that means on moving through function F(S) we are moving exactly by unit length. If you imagine this it seems true. Because no matter where the curve is going its length get incremented in equal length.<br />
<br />
So how we can find the equation for F'(s) ? Intuitively we can think like this. Anyway F(s) and F(t) represents same curve , only different is magnitude of F'(s) is 1 , But F'(t) may not be 1. But both these vectors points to the same direction. right ? so we(I)can conclude like this<br />
<br />
F'(s) = F'(t) / || F'(t) ||<br />
<br />
<br />
Other-way is like this.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi23x3ISFA7-rErfWn_jkNOEV5IQyL6Xz6QpSPYlWOGWLSTM1Mgj0g3fmxJilo6uj-49yWSwFlxTmFuyr_1A7-HcGBVBSoq2yJ97N2oN598-thyphenhyphenw7kHIjTki6Mf5pHU1Z2X6Qp6GASjhiI/s1600/curve+length.JPG" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="59" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi23x3ISFA7-rErfWn_jkNOEV5IQyL6Xz6QpSPYlWOGWLSTM1Mgj0g3fmxJilo6uj-49yWSwFlxTmFuyr_1A7-HcGBVBSoq2yJ97N2oN598-thyphenhyphenw7kHIjTki6Mf5pHU1Z2X6Qp6GASjhiI/s200/curve+length.JPG" width="200" /></a></div>
<br />
<br />
<br />
<br />
<br />
Now Differentiating both sides with respect to t.<br />
<br />
ds/dt = || F'(t) ||<br />
<br />
If we differentiate function F(t) with respect to s (length) we get<br />
<br />
= F'(t) * dt/ds (chain rule of differentiation)<br />
= F'(t) / (ds/dt)<br />
= F'(t) / || F'(t) || ( we know ds/dt = || F'(t) || )<br />
<br />
that is dF(t)/ds = F'(t) / || F'(t) which is eqult to F'(s). This is fantastic. :)<br />
<br />
Now Next step is finding F''(s) , I will explain that in next post. It is time to sleep.<br />
Nowadays days I am getting more into mathematics than software engineering. To really understand things you need to have great patience and curiosity. After all these years , I am still a novice.<br />
<br />
<br />
<br />
testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-58247143797554440692012-07-16T21:55:00.002+05:302012-07-16T22:04:21.869+05:30First steps into Robotics.<br />
First steps into Robotics.<br />
<br />
Yes , I decided to start looking into the interesting Robotics domain. Since i am not an electronics/mechanical engineer, i don't have any plan to build my own 'kd' Robot. My interest is in computer vision. I just want to study how these systems can be practically implemented. Like how we can program a small car for automatic parking on your Dining table!.<br />
<br />
<span style="background-color: white;">For starters , it is difficult to find some good starting point.</span><br />
IF you have money to spend , you can buy <a href="http://www.parallax.com/eddie" target="_blank">eddie</a> , Which supports microsoft RDS. <br />
Following picture shows eddie.<br />
<img src="http://tinyparades.files.wordpress.com/2012/02/eddie_assembled.jpg?w=500&h=396" />
<br />
<br />
<br />
For others, there are couples of basic robots like <a href="http://www.parallax.com/ProductInfo/Robotics/tabid/229/Default.aspx" target="_blank">Boe-Bot</a> which is cheaper and has some basic sensors.<br />
<br />
<img height="449" src="http://www.parallax.com/Portals/0/Images/Prod/2/281/28132a-L.jpg" width="640" />
<br />
<br />
<br />
mmm... Thats all for now. God knows how will it ends up.testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-87158092528664194492012-04-18T21:48:00.003+05:302012-05-24T09:30:58.429+05:30Frequency Identification<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">In this post i will try to explain the basic things to identify major frequency components from a data.This helpful filtering certain frequencies from the source or for doing some analysis. Frequency analysis a must learn thing if you are learning image processing, signal processing.</span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Basic idea is to convert the data to frequency domain using discrete fourier transformation, and using that we can find the major frequency in the data.Before going to the details lets look the equation of a basic Sin wave</span><br />
<div>
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">it is sin( 2*Pi/T * t )</span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">where T is the time period of wave</span><br />
<div>
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"> t is the instantaneous time.</span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"> Pi Ofcourse 22/7 , </span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Lets plot this wave. I am using mathematica to plot the wave. </span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Here is the wave form</span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">T = 20</span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Plot[ Sin[2*Pi/T*t], {t, 0, 50}] . (</span><span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">We can verify T =20 from the graph.)</span><br />
<span style="font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span><br />
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAggkf0fqfkJD7q7SjfspEL8eGgylCW5tRJTHmyh5ZgBJq9z2QChRZRaz06kGGnivb_66y2SEXwRjaSyIEbo2bfmDMWHU2ODzSHqeYmWQ8CzOhlNorb4CfQY0bfkILrLpNgAZUTIW7f9M/s1600/sine.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em; text-align: center;"><img border="0" height="253" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAggkf0fqfkJD7q7SjfspEL8eGgylCW5tRJTHmyh5ZgBJq9z2QChRZRaz06kGGnivb_66y2SEXwRjaSyIEbo2bfmDMWHU2ODzSHqeYmWQ8CzOhlNorb4CfQY0bfkILrLpNgAZUTIW7f9M/s400/sine.png" width="400" /></a>
</span></div>
<div>
<div class="separator" style="clear: both; text-align: -webkit-auto;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">So the frequency of this wave is 1/T . that is 1/20.</span></div>
<div class="separator" style="clear: both; text-align: -webkit-auto;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Ok. this is no big deal unless you are very weak in mathematics. Now lets add some random noise to it</span></div>
<div class="separator" style="clear: both; text-align: -webkit-auto;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both; text-align: -webkit-auto;">
</div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">n = 1500;</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">T = 20;</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">SampledData= Table[Sin[2 Pi* x/T] + RandomReal[.8], {x, n}] ;</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">ListLinePlot[SampledData]</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="background-color: white; clear: left; color: black; float: left; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="241" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjTHfgYfQOGkd53boeRRM_jlSQc2ed3WxwOe7B76-YUG9lnQK6ZxW4cbqgQPxeJK5tiQOvqOeHHyU5Z2S841tZ3eCqj7hDncodsjXwTY29l2DC78jaowzVPmUlqQGWm37a3VLJ7rsRzVU/s400/noisy.png" width="400" /></span></div>
<div class="separator" style="clear: both;">
<span style="font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">I hope now you cannot identify the frequency from this ;) .</span><span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Lets find the T period from this , it must approximate to 20.</span><span style="background-color: white;"><span style="font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Before that lest look the equation of one dimensional DFT</span></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="background-color: white; clear: left; color: black; float: left; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpkzyNe2Z_52Udfs2oZL9BjEpkvm4k15S4_iiyyWSD-ZMRsGXObh82Di67gyYYpo_1NnEOHg7KGLE5bbeWED2ZKIzVLrslcsKsMLqO5nEfaMOPKCAULDvXP6soje6e58cxwHgjn-6CLoQ/s1600/dft.png" /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white;"><span id="goog_1683762661" style="font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"></span></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Where N is the total number of elements and k/N will give the frequency (because Sin (2*Pi*f * n ) .</span><span style="background-color: white;"><span style="font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Ok , now i am going to do DFT with data generated with equation Sin[2 Pi* x/T] and I am going to find the power spectrum(magnitude of complex numbers)</span></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">DftData = Abs[Fourier[SampledData]];</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">lets plot the power spectrum graph</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="background-color: white; clear: left; color: black; float: left; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="246" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht3Uqm8P077kMV0nM0kXLN6pktPmmf8bw9B_jHJaVsL_-ZYcz41Nb_FCzJlz_zJx_fJNsI6HL9aU5lfy_F0yiW6dOubNsWoYnznVhqVZ7jNQbRV0vflqZidTcnsJwAepxq1TqUOUeLtkA/s400/power+specturm.png" width="400" /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">In graph you can see two spikes. The rightmost spike represent the nyquest frequency( i will explain it later). lets find the first position where magnitude is highest.</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">pos = Position[f, Max[f]][[1, 1]]</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">it will be at 76.</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Now we can find the frequency by substituting this value for k in equation k/N .</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">that is 76/1500 = .0506. which approximates to 1/20.</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">If you want to find the timer period just find the reciprocal. </span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">T = 1500/76 = 19.73!! approximates to 20.</span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="separator" style="clear: both;">
<span style="background-color: white; font-family: 'Helvetica Neue', Arial, Helvetica, sans-serif;">Hey you just learnt a great thing!!. </span></div>
</div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-44231703334807622482012-04-12T22:58:00.001+05:302012-05-24T09:30:58.350+05:30MD2 animation<div class="separator" style="clear: both; text-align: left;">
Before 2 weeks I added Md2 animation support to my engine. It was an easy task. MD2 has some predefined set of animations. MD2 is used by games like QuakeII,<a href="http://en.wikipedia.org/wiki/SiN_(video_game)">Sin,</a> <a href="http://en.wikipedia.org/wiki/Soldier_of_Fortune_(video_game)">Solider Of Fortune</a> .</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
See the MD2 animations running with my engine(Video lacks clarity because my screen capture software not allows to record at high frame rate with good quality)</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.blogger.com/video.g?token=AD6v5dxrs-8jyA6eVJ1qFhortEhELPxJJ09ya3wDX2ZzuaDyJ2HPaQOLKOUZn-x2vsatpX9ktJguWcIETHVVu9aGRA' class='b-hbp-video b-uploaded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
While coding MD2 loader i found that the skin path in the MD2 file is relative and sometimes entirely in some other directory. So we cannot rely on this path. In MD2 file they are trying to minimize the model data by using different techniques like having predefined normal vector set. The creators also store texture coordinates as short rather than float.you need to divide by the size of texture to get the real texture uv coordinates.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
One other problem is with inconsistent naming convention of frames. say we have 120 frames , and in one Md2 file 10-20 frames contains animation for running data with name "Run001", but in some other file they use "Run__1".. it would be better if the creators have made a standard for frame names.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Finally you can use <a href="http://www.blender.org/">blender </a>modeler software to create MD2 animations.(i heard it is buggy :) , Thats ok Bugs are everywhere), </div>
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com1tag:blogger.com,1999:blog-3996848416074637521.post-10442596400944390572012-04-11T15:24:00.002+05:302012-05-24T09:30:58.283+05:30Gaussian filter<br />
Gaussian Filter modifies the input data by convolution with a Gaussian distribution. Gaussian filter is often used to smooth out images.In this post i will try to show the frequency response of Gaussian filter. It is very important to understand the frequency domain behaviorism.When we consider the frequency response of gaussian one diamension filter we can see that , the filter reponse is inversely proportional to the frequency, lower the frequency, its response is high, that is more smoothing happens to lower frequency components.<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
An unnormalized Gaussian distribution is </div>
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKfkRP_92R6djFnRiDbmuS_Or_wV_i2J2G7haNaCf3bWeoEivukTzjMscvvbdJ6JUVhGuWczEmbqmshQuRK464j2hvWcfTJAcwC8v-0xj2ECohzP9GixE3M2efmRprraBwbrdqYhKzAwA/s1600/gaussian.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKfkRP_92R6djFnRiDbmuS_Or_wV_i2J2G7haNaCf3bWeoEivukTzjMscvvbdJ6JUVhGuWczEmbqmshQuRK464j2hvWcfTJAcwC8v-0xj2ECohzP9GixE3M2efmRprraBwbrdqYhKzAwA/s1600/gaussian.png" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em; text-align: left;">where <a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRNEKU3U9ZIjulMmT6IZjlMSJvle-aL_pjdX9GvG7S240BEZ8IMmz0YjwmKKxqbRg2YhMV6YSlOCqQGYKpXxSBqQyVqO7eptQqbMaQ9yiGHQCPTOGurTaCjBCZEroWGwktyhXad_3Vjig/s1600/sigh.png" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRNEKU3U9ZIjulMmT6IZjlMSJvle-aL_pjdX9GvG7S240BEZ8IMmz0YjwmKKxqbRg2YhMV6YSlOCqQGYKpXxSBqQyVqO7eptQqbMaQ9yiGHQCPTOGurTaCjBCZEroWGwktyhXad_3Vjig/s1600/sigh.png" /></a>is the standard deviation. This function is will form a belll shaped curve with center at 0. This function is non zero every where(high value at center and decreases ). curve is shown below</span><span style="margin-left: 1em; margin-right: 1em; text-align: center;"><span id="goog_1910026305"></span><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Gaussian_Filter.svg/220px-Gaussian_Filter.svg.png" /></span></div>
<div style="text-align: left;">
A normalized gaussian distribution can be found by normalizing the above equation with the total area, which can be found by integrating it over -Infinite to +infinite. </div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYG2LjVkdcEbmKo-1Zh8Z_-oERSlQObsR_pdS7QqZGDcJM8RnTssy8NHv-6pXJeuJWwFEmx6245aeDX_4oJAU5h6X0vv4H3V6tWQHp3WZV8qDlHTdf8F9sm-9sLc9VPuoSEMbdh-XyoIw/s1600/gaussian.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYG2LjVkdcEbmKo-1Zh8Z_-oERSlQObsR_pdS7QqZGDcJM8RnTssy8NHv-6pXJeuJWwFEmx6245aeDX_4oJAU5h6X0vv4H3V6tWQHp3WZV8qDlHTdf8F9sm-9sLc9VPuoSEMbdh-XyoIw/s1600/gaussian.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
so the normalized equation is(from wiki) : <img alt="g(x) = \frac{1}{\sqrt{2\cdot\pi}\cdot\sigma}\cdot e^{-\frac{x^2}{2\sigma^2}}" src="http://upload.wikimedia.org/wikipedia/en/math/a/3/2/a32eef2d113622a2b1c047563690a588.png" /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div style="text-align: left;">
Frequency response of a 1-D Gaussian filter can be found by doing DFT over the 1-D kernel,<br />
<br />
We can find it in mathematica simply with following commands<br />
<br />
DftResults = Fourier[ Table[PDF[NormalDistribution[0,1],x],{x,-3,3,.01}] ];<br />
ListLinePlot [ Abs[DftResults],PlotRange->All ]<br />
<br />
This will plot the power spectrum of Gaussian 1-D filter. It will look like this (X axis-frequency,Y axis magnitude), we can see that at lower frequency level , filer gives better output.. the extreme right shows the nyquist frequency( ignore that for now. ). From this we can see Gaussian filter act as a low pass filter.</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="text-align: left;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmMcg7l1ynhD6HyAasVR7L5QfG7CPfaMls8JdQZxuJNfgmiNw4Sb5BeYMMNXsQbQgNqoE3lihiukGYW1_P2zs7ZznF4naC3z9tqN3j0doqNzRRCS1JY1duOjv1NvLCfvXCUNRpLVXyVDk/s1600/gauss+freq+response.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmMcg7l1ynhD6HyAasVR7L5QfG7CPfaMls8JdQZxuJNfgmiNw4Sb5BeYMMNXsQbQgNqoE3lihiukGYW1_P2zs7ZznF4naC3z9tqN3j0doqNzRRCS1JY1duOjv1NvLCfvXCUNRpLVXyVDk/s320/gauss+freq+response.png" width="320" /></a></div>
<br /></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<br /></div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-29439697379732238652012-01-23T20:40:00.000+05:302012-05-24T09:30:58.318+05:30GFD(Generalized Fourier Descriptor), Part 1it is interesting.. GFD is a rotation invariant. In GFD the orginal image is transformed to polar cordinate system. This provides the rotation invariant ability. I will explain how this happens. When we map normal image in cartesian coodinate system to polar coordinates, a rotation in Cartesian coordinate will cause translation/shifting in polar system. Remeber in polar system r, and theta are the axis. So when you rotate original image, R remain same so in effect the coresponding image is shifted(to left/right according to the direction of rotation) in polar system.<br />
<br />
Still you may be wondering even if that is the case, why Fourier transform output remains same ? because we are operating on different data.For each rotation , the image is shifted in polar coordinate system.<br />
If you thought like that, you are thinking.. Good.<br />
<br />
I will explain the answer to the above puzzle.<br />
<br />
<img alt="X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi \frac{k}{N} n}." src="http://upload.wikimedia.org/wikipedia/en/math/d/5/4/d546ba719f01a0419c5bbf84e8f9c495.png" />
<br />
<br />
If you remember one dimensional Fourier transform you can see that we are finding the dot product of our Image data with a number of Cos,Sin vectors (N diamensional, same as image size). The sin and cos are orthonormal , so the magnitude remains same. Please read my previous post <a href="http://cgmath.blogspot.com/2011/12/image-recognition-using-phase-only.html">http://cgmath.blogspot.com/2011/12/image-recognition-using-phase-only.html</a> to get an intuitive grasp on DFT.<br />
<br />
that is<br />
<br />
Magnitude Of DFT[ {1,2,3,4,5,6}] is equal to Magnitude of DFT[ {4,5,6,1,2,3}]<br />
<br />
Magnitude is Sqrt( i*i + j*j ) of the complex number.<br />
<br />
Thus we get rotation in-variance. Now the next thing is Fourier descriptor. I will post about that after some days. It is simple( Really ? )<br />
<br />
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-68860410756996813212012-01-10T00:47:00.001+05:302012-05-24T09:30:58.390+05:30Just started with generalized Fourier DescriptorI started working on a new algorithm for image search. This is based on Fourier descriptor. Image is first converted in to a corresponding polar representation.This representation allows to get complete rotation in-variance. This is Because a rotation in Cartesian plane corresponds to a angle shifts in polar domain. So the DFT remains same. This is a simple and great idea.<br />
<br />
I also started working on my Engine to add MD2 animation support. The image processing things takes too much thinking time also sometimes makes me dull. Thats why i started this to feed my interests.MD2 animation is simple to implement also to understand. Bone animation is difficult to understand if you are a beginner/intermediate in computer graphics. You may be wondering about which format should be used like that.. I had a looked that before some years. But at that time i didn't got time to implement it. Now sadly i am not remembering much.I should have implemented it that time.<br />
<br />testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-69534146442366371382011-12-13T23:26:00.005+05:302012-05-24T09:30:58.395+05:30Image recognition using phase-only correlation<br />
I have been working on image matching program which based on frequency analysis.Phase correlation principle is used here.<br />
<br />
The concept is like this<br />
<br />
<ul>
<li><i>Get different frequency information from image using DFT</i></li>
<li><i>Do phase correlation of source and templates frequencies (got from source and template images, both are n-dimensional)</i></li>
<li><i>After phase only correlation do inverse Fourier and find the peaks in the real part. that peaks shows the matching positions.</i>.</li>
</ul>
To really understand how this works , you need to know how DFT works. Not just that magic equation.<br />
How it could transform the signal(here image) to freqency data ?infact we can make an intutive represenation of DFT equation in mind. Here it is in without any formulas.<br />
<br />
You need to know the vector projetion operation first. If you don't know that my humble opinion is you better learn some basic vector maths right now. (vectors are everywhere.. Beware!!).<br />
In DFT we have an image, which can be represented as an N-Dimensional vector.Then we take the dot product of this N-dimensional vector with an another N-Dimensional vector , lets call it 'Sin' vector, we also take dot product with an another vector, lets call it 'Cos' vector<br />
<br />
that is (ImageN . Sin) + i (ImageN . Cos ) : "<i>. is Dot product between vectors "</i><br />
<br />
(Dot product is actually gives the distance in terms of vector, you can conceive it as projecting the image data to n-dimensional sine and cosine vectors which gives the real and imaginary parts). We do this operation for a number of frequencies, so the Sin,Cos Vectors changes giving different n-dimensional vectors.That's how you get the output N complex numbers (Now look refer the original DFT equation)<br />
So what we just said is, we project(DOT) the image data to a number of vectors which are obtained from different sin,cos signals. Another point worth to remember is Sin and Cos vectors are always ortho normal ). I hopes i just wrote enough theory for DFT so that you can understand it intutively.Visualization is very important.<br />
<br />
So back to matching thing., we do DFT of source and template image( both are same size, template can be padded with zero ). After this apply phase correlation using equation<br />
<br />
(a+ib)(p+iq)* / (| (a+ib)(p+iq)* | )<br />
<br />
<ul>
<li><i>(a+ib): complex number got from source DFT (so for NxN dimensional image , there will be N*N complex numbers,represented as 2D array NxN.)</i></li>
<li><i>(p+iq): complex number got from template DFT, (p+iq)* is conjugate operation.</i></li>
</ul>
<br />
<br />
What this equation does is it gives high values for signals where where peaks and bottoms correctly<br />
aligns each other.<br />
<br />
<br />
Now we do inverse DFT on the phase only correlated datas, and apply some threshold on the real part inorder to get the peaks which indicates the matched positions<br />
<br />
Images from my tests.<br />
<br />
Original image (after edge detection)<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB4wfrIxBAnzc-JvMWQ7zm-P16LIEcCmjTWbFndeNPcSkkl60mMTIVUUzCseGOkhg4fJm3f0tLcHkAvlGQjZaQJxIsl0qhoEve8ZGn7T6WE2auT3qt7wQFDXwIwz4QHrf6ab6D65YD1sI/s1600/o2.bmp" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB4wfrIxBAnzc-JvMWQ7zm-P16LIEcCmjTWbFndeNPcSkkl60mMTIVUUzCseGOkhg4fJm3f0tLcHkAvlGQjZaQJxIsl0qhoEve8ZGn7T6WE2auT3qt7wQFDXwIwz4QHrf6ab6D65YD1sI/s1600/o2.bmp" /></a></div>
<br />
<br />
Template image (template image size must be same as source, so pad remaining area with zeros)<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie4Q-wD4I83GLz3oq5kwbRnpPHihoczSP9reokWzPxSo5SVTi2u8ZoiaoN4Kxr-S97WEBd94VL8sqkDvDIDHE1d29qmnkki0Rtws2c8k5t6cJtX056VrZJspndP30tMJ4f8GpFY2kjUNs/s1600/t2.bmp" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie4Q-wD4I83GLz3oq5kwbRnpPHihoczSP9reokWzPxSo5SVTi2u8ZoiaoN4Kxr-S97WEBd94VL8sqkDvDIDHE1d29qmnkki0Rtws2c8k5t6cJtX056VrZJspndP30tMJ4f8GpFY2kjUNs/s1600/t2.bmp" /></a></div>
<br />
<br />
Result after phase only Correlation, see the peaks, You can see some invalid peaks also there (that is another story). I did this with mathematics. With 'mathematica' or 'matlab' implementation is easy. But i had to spend months to really understand the theory.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3FIfqWU_ApG264O2MVDSK61SQBqj0fxhvyFp1KYqhijqnR9vHnm6HSQMErM05aFu9kHgbJI-Kferq6gxqa4YZoM306ST5esVsTg5Kq5zUErqYSdScmcYqLXUmCt9lyVo2f6Hqu4JAmhQ/s1600/result.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="450" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3FIfqWU_ApG264O2MVDSK61SQBqj0fxhvyFp1KYqhijqnR9vHnm6HSQMErM05aFu9kHgbJI-Kferq6gxqa4YZoM306ST5esVsTg5Kq5zUErqYSdScmcYqLXUmCt9lyVo2f6Hqu4JAmhQ/s400/result.png" width="545" /></a></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
This method has advantage of being small invariant to smaller rotation and scale. But drawback is it needs higher time for processing due to DFT.This algorithm doesn't consider any shape information for matching, so this can give false results when too much edges present in source image.<br />
<br />
That's all for now,this was a quick post. Good Luck with your projects.testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-79658452758298708972011-06-26T22:34:00.001+05:302012-05-24T09:30:58.414+05:30A Board game within 3 hoursYes, I made a board game within 3 hours. I don't know what made me to code it. May be after playing some board games in mobile, I wished to create my own, especially those crystals graphics. I learnt to create some nice looking glass buttons with Gimp, it is just silly task but it is fun.<br />
<br />
See game image shown below(the red text indicates the connected cells count to it), the game idea is like whoever first able to make 5 coins in a line(vertical,horizontal or diagonal) will win the game.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgii9NyYlYjtaMmwjF_ujLqzz_kzgXHRUfmKw6IXc4S_oDUHedX2W3teaY8nvSL-dlmOSjHydIB2CyhWxtEmzd4__qvaOY7U5EuQA4VEULpicF4C9BreThUcoxgucndBIBXhtBqcfCJr-8/s1600/board+game.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgii9NyYlYjtaMmwjF_ujLqzz_kzgXHRUfmKw6IXc4S_oDUHedX2W3teaY8nvSL-dlmOSjHydIB2CyhWxtEmzd4__qvaOY7U5EuQA4VEULpicF4C9BreThUcoxgucndBIBXhtBqcfCJr-8/s320/board+game.png" width="310" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: left;">I coded the AI for this small game, it was fun and so easy, just count the number of opponent(player1) connected coins and calculate probability for each empty cell. Next is to calculate the probability of player2's connected cell, based on these determined the cell where the computer must put the coin. It works!!, Can be made better by adding some other ideas too(like considering the distance , so that if same probability comes it will choose the cell which is more connected). </div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">[if you need source code mail me.]</div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com1tag:blogger.com,1999:blog-3996848416074637521.post-46585910863180505122011-05-11T23:34:00.001+05:302012-05-24T09:30:58.361+05:30Shape Context MatchingI recently completed my shape context image matching project without much success :(.if you don't know about shape contexts , check out this link <a href="http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/sc_digits.html">SC</a><br /><br />The shape context can be created easily, For matching operation a bipartite based graph matching algorithm can be used. It can be done using Hungarian algorithm with complexity is less than the brute force method( O(n^2) ).<div>But after implementing Hungarian algorithm i am not able to find enough match point pairs between shapes. The problem with Hungarian method is that it can't give you the answer in fixed amount of time. It tries to optimize, sometimes never ending optimizations.</div><div><br />Still I believe it can be corrected(using a different approch to SC creation) , I need to work more. Not getting enough time.<br /><br />A nice lecture about Hungarian Algorithm can be found at <a href="http://www.youtube.com/watch?v=BUGIhEecipE">here</a></div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com0tag:blogger.com,1999:blog-3996848416074637521.post-33336576797593343402011-02-13T22:33:00.001+05:302012-05-24T09:30:58.329+05:30Face Detection using PCA.I have been working on my image processing library to support face detection. I started with basic method PCA ( Principal component analysis). Basically you need to have a set of images(20-50) with different lighting conditions etc. The next step is to create covariance matrix out of it and find the eigen vector. Then simply project the the image you need to check in to Eigen vectors and find the distance between them.Do some thresholding to classify it.One important thing is you don't have to take all eigen vectors,may be its better to sort (descending ) based on Eigen value and take only first 'N' vectors.<br />
<br />
See the video<br />
<div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.blogger.com/video.g?token=AD6v5dzWkv4bniopqUsNGJTgJpYXBvvzjLZ3-BEWahA6tsEXQRe-tkpWxqT9Xuen2dLXsjGX8U5aHJqb6G5Xp8BNtw' class='b-hbp-video b-uploaded' frameborder='0'></iframe></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: left;">The difficult part in PCA may be to find the eigne vectors , QA algorithm seems a good choice. The current problem with running time.It takes almost 1 second to process 200X201 image. Roughly O(n^3) complexity. I am plan to implement it in CUDA,so that it can be used for real time detection.</div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com9tag:blogger.com,1999:blog-3996848416074637521.post-43748005404580978872010-12-14T21:06:00.001+05:302012-05-24T09:30:58.339+05:30Number Plate region extraction<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">After a long break I started writing about my image processing studies.This time KD came with a project to extract number plate region from an image. The advantage of my method over other methods are the following.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">1. fast processing</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">2. It can give you multiple regions in image if more than one number plate present</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">3. It can handle image rotation up to a certain degree( +- 35 ) .I used Eigen vectors.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">4. No third party libraries like openCV or aforge ( yes some times i like to reinvent the wheels again )</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">See the video to see the project in action.</span><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='448' height='350' src='https://www.blogger.com/video.g?token=AD6v5dz0C5YLPH8XkmOJ-eJG9SFHomiV86Ixt3YRS-UY1P9w4ayiL9svdg8VKf8K2AZuYSFUJj2LM-HS5IjZ6SNIgA' class='b-hbp-video b-uploaded' frameborder='0'></iframe></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><br />
</div><span class="Apple-style-span" style="font-family: arial, sans-serif; line-height: 13px;">Although the number plate extraction parts works pretty good , I don't have a good OCR module. So i am having troubles to </span><span class="Apple-style-span" style="font-family: arial, sans-serif;"><span class="Apple-style-span" style="line-height: 13px;">extract numbers from image. I tried using a simple back propagation neural network, its quality of recognition is not that great.Now i am trying to develop a rotation,scale invariant recognizer. It may take another 9 or eight months to do that. But if it works i think that would be a great achievement<span class="Apple-style-span" style="font-size: x-small;">.</span> I will try to post more updates here.. </span></span><br />
<span class="Apple-style-span" style="font-family: arial, sans-serif;"><span class="Apple-style-span" style="line-height: 13px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: arial, sans-serif; line-height: 13px;">If you know any good optical character recognition library, please let me know. </span><br />
<span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: x-small; line-height: 13px;"><br />
</span>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com3tag:blogger.com,1999:blog-3996848416074637521.post-46332320480166078952010-06-12T15:19:00.006+05:302012-05-24T09:30:58.356+05:30Calculating the reflected ray/vector<p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;"><br /></span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">In computer graphics applications its often needed to calculate the reflection ray for example if you are writing a ray tracer, a shader for some advanced lighting , or environment mapping etc.</span></span></p><p class="mobile-photo"></p><div><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">If you are writing shaders , there are standard library function to do that . In cg shading language there is a function reflect(also its more efficient than writing our own).</span></span><div><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;"><br /></span></span></div></div><div><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">In this post rather than just giving the vector formula for reflection ray , i am trying to explain the simple mathematics behind that.</span></span></div><div><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;"><br /></span></span></div><div><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">See the following image, I is the original ray, and R is the reflected ray which we need to found.</span></span><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">N is the normal of the incident plane. P is the line perpendicular from normal to both rays. it is obvious that at both ends the length of P will be same.</span></span></div><p></p><p class="mobile-photo"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSTVj6UjiyGyJ_mUorUZR33VbTiFqbcTP1FOnFKTVcyELE3EsKw4ZvDflZIsSVmgWD0skcY3KwUaJvtXVGgOfB6K92OFHlq5q5QewxIhjJf-E4_W2l_UJLg350NasmbQJpqNtceaef7CY/s1600/reflect-724599.bmp"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSTVj6UjiyGyJ_mUorUZR33VbTiFqbcTP1FOnFKTVcyELE3EsKw4ZvDflZIsSVmgWD0skcY3KwUaJvtXVGgOfB6K92OFHlq5q5QewxIhjJf-E4_W2l_UJLg350NasmbQJpqNtceaef7CY/s320/reflect-724599.bmp" border="0" alt="" id="BLOGGER_PHOTO_ID_5481822774218251250" /></span></span></a></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;"><br /></span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span"><span class="Apple-style-span" style="font-size:medium;">Dot product between two unit vectors gives the cosine of the angle between them. </span></span></span><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">So using this idea we can find </span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">R = DotProduct[ I, N ] * N + P . ---> Eq(1)</span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">We don't know P now. But I + P = N * DotProduct[ I,N].</span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">So by rearranging P = N * DotProduct[ I,N] - I. Substituting the value of P now in equation(1) gives the final equation. </span></span></p><p class="mobile-photo"><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">Here it is the final equation </span></span><b><span class="Apple-style-span" style="font-family:arial;"><span class="Apple-style-span" style="font-size:medium;">R = 2 * N * ( DotProduct[ I,N] ) - I</span></span></b></p><p class="mobile-photo"><br /></p><div class="WordSection1"> <p class="MsoNormal"><o:p> </o:p></p> </div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com2tag:blogger.com,1999:blog-3996848416074637521.post-70070135672043011962010-03-16T11:49:00.009+05:302012-05-24T09:30:58.400+05:30Color Image Segmentation using Meanshift Algorithm<div style="text-align: left;"><br /></div><div style="text-align: left;"><span class="Apple-style-span" style="font-family:arial;">The meanshift method can be used to segment color image. </span><span class="Apple-style-span" style="font-family:arial;">In this method image pixels is treated as points in color space.In each iteration</span> <span class="Apple-style-span" style="font-family:arial;">the meanshift vector is calculated for points which are inside the kernel radius.After that the the old kernel location is changed to meanshift vector's position. Color is also updated. This process continues untill both converge.</span></div><div><span class="Apple-style-span" style="font-family:arial;"><br /></span><span class="Apple-style-span" style="font-family:arial;">Original Image</span></div><div><span class="Apple-style-span" style="font-family:arial;"><br /></span><span class="Apple-style-span" style="font-family:arial;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhto3F4s-MFixq_lML1-TPkUPJotRylxtglpvJ9rb6N41zRHGwqJZIQ47ZdrkAY4TXTu-YOmdSd3lAEXabLJHrllEzRNfLAYIC8X2d9h8SRa19P9LkhfTwaraIOcOb1oRotf6DtxacWoGY/s400/sachin.jpg" style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 294px; height: 400px;" border="0" alt="" id="BLOGGER_PHOTO_ID_5449259186661071154" /></span><br /><span class="Apple-style-span" style="font-family:arial;"></span><span class="Apple-style-span" style="font-family:arial;">Meanshift Filterd Image</span><br /></div><div><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgL0An-Y02hkFlQZj8STbgOmV3pZJMA1uXugKUj3HN6BB_FakS-vtYL4r9Op2rNSpNf1XmTDQV1tSWvlsAoRqnrwBIcnxPM8ui3b8ZzXP_4ujdi2FW5yLOBTJXZjGRYbKFK56_UFZYwwtM/s400/Untitled.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5449259193015402594" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 391px; " /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: left;"><span class="Apple-style-span" style="font-family:arial;">As the iteration count increases , the same color segment which has same type of colors will get merged together. You can see the effect of meanshift filter on sachin's photo.Its like water painting (not exactly,there are other filters for that. )</span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div>testhttp://www.blogger.com/profile/03784579986960576423noreply@blogger.com26