tag:blogger.com,1999:blog-10268706315991979192024-02-18T17:35:59.864-08:00Recognizing Sketch RecognitionGirish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.comBlogger36125tag:blogger.com,1999:blog-1026870631599197919.post-24982892803859269572015-12-12T21:59:00.001-08:002015-12-12T22:00:01.143-08:00Reading 35: Enhancing KNN Search in Spatial Indexes<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Cheung, King Lum, and Ada Wai-Chee Fu. "Enhanced nearest neighbour search on the R-tree." <i>ACM SIGMOD Record</i> 27.3 (1998): 16-21.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://delivery.acm.org/10.1145/300000/290596/P016.pdf?ip=165.91.49.42&id=290596&acc=ACTIVE%20SERVICE&key=B63ACEF81C6334F5.79B51EFA2DE92FE8.4D4702B0C3E38B35.4D4702B0C3E38B35&CFID=737578439&CFTOKEN=11290610&__acm__=1449986375_0fc30a6a7c8fa35a2bd0af72b15f01f3">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper gives an improves set of heuristics for the R* Tree, that makes indexing and retrieving neighbours of any spatial object, much more efficient.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
We perform relative indexing primarily by extracting the nearest neighbours of a drawn feature, and checking how much the relative position of the two features match. However, this approach fails drastically when we have insufficient features indexed. In such a case, we have to resort to conventional algorithms that are translation independant. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-71468721470629540942015-12-12T21:52:00.000-08:002015-12-12T21:52:46.955-08:00Reading 34 : 2D Curve Similarity Algorithms<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Deriche, Rachid, and Olivier Faugeras. "2-D curve matching using high curvature points: application to stereo vision." <i>Pattern Recognition, 1990. Proceedings., 10th International Conference on</i>. Vol. 1. IEEE, 1990.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=118103">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper deals with the high curvature points of curves, and uses derivatives to calculate curve maxima. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Our application requires us to be able to gauge the similarity between two freely drawn curves, and we expect a very optimistic approximation of correctness between a template and candidate curve in the case of rivers.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Although the curve detection methods presented here are for a computer vision domain, they can be easily translated to the sketch domain.</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-60698351555224120552015-11-28T21:56:00.000-08:002015-11-28T22:20:55.641-08:00Reading 33 : Using shape context for sketch recognition<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">Citation: </span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">Belongie, Serge, Jitendra Malik, and Jan Puzicha. "Shape matching and object recognition using shape contexts." <i>Pattern Analysis and Machine Intelligence, IEEE Transactions on</i> 24.4 (2002): 509-522.</span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><a href="https://www.cs.berkeley.edu/~malik/papers/BMP-shape.pdf">Publication Link</a></span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">Summary:</span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">This paper is very similar to the $p algorithm, in the fact that it tries to match every point in the candidate to some point in the template. We take the set of vectors originating from a point to all other sample points on a shape. These vectors express the configuration of the entire shape relative to the reference point. </span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"></span></span><span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">Discussion: </span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">The following library has Javascript implementations of Haudroff Distance and Shape Context. This was the motivation behind looking unto Shape Context as an alternative means of template matching.</span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span></span>
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">https://github.com/kjkjava/Sketchy.js/tree/master</span></span><br />
<br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"> <span style="font-family: "times" , "times new roman" , serif;">The shape <span style="font-family: "times" , "times new roman" , serif;">descriptor </span>of<span style="font-family: "times" , "times new roman" , serif;"> a point is represented as a <span style="font-family: "times" , "times new roman" , serif;">relative dist<span style="font-family: "times" , "times new roman" , serif;">r<span style="font-family: "times" , "times new roman" , serif;">i<span style="font-family: "times" , "times new roman" , serif;">bution <span style="font-family: "times" , "times new roman" , serif;">over pos<span style="font-family: "times" , "times new roman" , serif;">itions<span style="font-family: "times" , "times new roman" , serif;">, <span style="font-family: "times" , "times new roman" , serif;">in histogram bins o<span style="font-family: "times" , "times new roman" , serif;">f log<span style="font-family: "times" , "times new roman" , serif;">-<span style="font-family: "times" , "times new roman" , serif;">polar <span style="font-family: "times" , "times new roman" , serif;">space. The cost of this matching for a poi<span style="font-family: "times" , "times new roman" , serif;">nt is defined <span style="font-family: "times" , "times new roman" , serif;">using the <span style="font-family: "times" , "times new roman" , serif;">chi-square statistic<span style="font-family: "times" , "times new roman" , serif;">:</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> </span></span><br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAABKCAIAAAAaD5VmAAAAA3NCSVQICAjb4U/gAAAS4ElEQVR4Xu2dZ7AVRROGARERAwoi5ogBFcWAZcQAAlpmBUUtM5gTKOZSwVAqggmzlpiwDIgRRQUjBgwEc85iQMw5PV9NfVPLzM7unD27e2avfX/cuneme6bn3bN9unu6Z5r/888/zar/M2bMmE6dOnXp0qVDhw7jxo3r0aNH9dckKxAEBAETgRZmQwX/nzBhQrt27bp169a6deu+ffuOHj26gosQkQUBQSAdgcorrGnTps2aNat3795qrYMHDx4/fvyUKVPuuOOO9NULhSAgCFQKgeZVdwl//fVXDKso5p9//vkLL7yw0UYbtW/fvlLPQoQVBASBFAQqr7BS1ifdgoAg0IQQqLxL2ISehSxFEBAEUhAQhZUCkHQLAoJAOAiIwgrnWYgkgoAgkIKAKKwUgKRbEBAEwkFAFFY4z0IkEQQEgRQERGGlACTdgoAgEA4CorDCeRYiiSAgCKQgIAorBSDpFgQEgXAQEIUVzrMQSQQBQSAFAVFYKQBJtyAgCISDgCiscJ6FSCIICAIpCIjCSgFIugUBQSAcBERhhfMsRBJBQBBIQUAUVgpA0i0ICALhICAKK5xnIZIIAoJACgKisFIAkm5BQBAIBwFRWOE8C5GkZgQef/zx5ZdffsiQIR988AHMd999NyfN3nfffTUPJAz/R4AjiK+55prrr79+wIABr776amjAyImjoT0RkacGBP7666+lllrqww8/bNWqFUdjT506tVevXnPNNVcNQwjpnAg89thjALjppps+8sgjZ5xxxpNPPhkUQmJhBfU4RJjaEMAEWHnlldFW/IHa2nrrrUVb1YagRf3RRx/dfvvtNK+00kpvvfWW1d/gBlFYDX4AMn09CDz11FMbb7wx9ySdcsopG2ywgedQ77zzTteuXffdd98//vjDk0WT4TFdeuml33//vYsRo+/iiy/+/fffXQRFt2eQ8PLLL991113BENn69+8/dOhQ/njiiSd69uxZtLS1ji8Kq1bEhL4oBHjTbrvttsMOO8x/AhwWFMTaa689ffp0Fcby5N1xxx0J08w999zQjxo1atlll73gggt8eEeMGIGyW3DBBRWxzYuJt9122+FM+YzmSWPPksCYQcJDDjlk+PDhakwwWWihhX7++ec777zzkksuSZioIV2isBoCu0xqInD//ffzkhPu/e6778w+x/8ouGeeeeakk05abLHFDjjggCuvvNJBmNKMisSp3HDDDVPomjV7//33sc422WQTTRnLyz7APPPM8/TTT6cO6EkQO0ssby4SAux5552H2cX9xLGzNLIR4eRHEAgEgeOPP37PPff0FAaTCttKEX/22WdLLLEEl1T68L799tunnXaapvzkk0/atGnz22+/pfIeffTRXHkZJYN3vvnmwwE0eL/88svddtstdUBPghIkRNOdfPLJSp6bb775vffe4+97773XU8LSyMTCauS3hcydGYFXXnkFi6xFixZoEAb59NNP0RqDBg1C79Q6JvtiGE0YWcmMvJPPP//8OuusEyVTvMq1jLZ36NBh5syZv/zyS/KYnr1lSoiXfdRRR2211VbLLbfcFVdc4SlhaWQtS5tJJhIEckRgjTXWuO666/SA66233ldffZVtfNQBMazLLruMK8Tvuece3lJ8THuo1157jbvEmzdvHu2Cd4sttqBl3Lhxs2bNmjhx4k033aRounTpMmnSpG222cYeqtaWMiUkoSEzkrWuKwO9WFgZQBOWJoUAamWBBRYg8Lz//vu3bduW7NPY5eFIoteMLnhRWPhQOKf4pMSqtUZbcsklYYkdqtbG8CWsdUWZ6UVhZYZOGJsCAh9//DG+2+mnn64UDQ5mx44dowtjm195dtgdqLNoF7wkf8FC/he6jN933XWXJiBinYupkirhueeey+YD8zZKwjI/B+ISlom2zJURgW+//RY3jfgU+QTYMrGjkFQ1e/Zs/LJvvvnmzz//1DQolHXXXTeWhUa8rc022wwLi7+JlLMJuPnmm0eJx4wZo/4lhmX7gzhQbAgSjCegxuZglJH42t9//23PSzqFq3hoxRVXRPsYLKkSslORr4S2zOG0iMIK51mIJE4EyAw69dRTyWz88ccfzzrrLJJFnaTNmqFZMHzIKmBjnt8kE6EjXPSogy233FL1koDK38xFiQ/JVgbLoosuatTWwbv99tuTUYERdOGFF1500UVvvPHGqquuqhhRsoaxptpJWOXHJY/dXr6EtgzhtIhLGM6zEEmakQXKTywQJ5xwAqYQNgt5D+iCWBrViB3EDhdk5ME/+uijFEgnuGZRdUAu2A477MCOPk4iQ7377rvEs3RCKaUqdEXnhVdF3JF54YUXxnNUW5aKhqyLTp06Jcjp2ZUsIUr2xBNPVEM1SkLPheRCJgorFxjzHwQzIbkEJK8pG15Kohby7LPPkhtFdjUqBkvq4YcfNhZIBjkbcASGsJ4GDhwIPj4IYDFRGeeysLDX2Blca6211FAQowopSenduzctOJhsC+Jjqt7VVluNXj0vvPPOOy9bgfTusssuEF911VXkuGupXn/9dW27+YgaS5MsIUm2BM6AroESxopdYGNpGV9FT8SjHTZsGDnB+A7EULHP+cbDXC963mzjp0pLqQQZMdkGr5ULw4F88Vq58qUnPsXzIvbED3+4UkDHjh2rXgZy4v0F4JWOEhuJownj8PnBDdQE5Hk999xzCfS6i0TWvn37+lDWScOz22+//eqXMJo4WqdIhbL/z+FvAj+Y/cRK+a3X8uabbxKG2GuvvQJcXaq0fAoPPvjgMiUnZowDVeaMmecCGXQWuemYMNkG8VRY6FBMJOJTaB81EU7ioYce6jMpeE6ePNmHsk4aFPcNN9ygB8ksYVUUVlNwCW+99VZs8quvvrp79+7aFuXUERRWjx49CrROMw3tIy3l/gceeGCm4TMykYUUYKVr7GIIKuGdkfFEwkGGvPbYMWMb0QJrrrnmiy++uPjiiyuCFVZYga3A1COiOJXlp59+8ilOjJ23pkaVCKZZApSwpuWkEld+l5BvS/Zc2Ay2A5ykxtQfRMBDOfbYY6Pb5AambGnbU7tw95GW94QSEGruXYMU0a5LSYjLFDF+jmNiW5FqsP7667OXx44+23MZBicxnaA4X3J2VY0ejXyFkSNHGoMPHjyYsxMIe+kDGwwCYoIE74lOZJCqJpYpU6aQ7v/1119zhGGUMYOEbKcSOtT7mzWJUTJx5U8c3X333QkrsJ3Mx8vAjvoyso3rB5S8ntiEGjUy20P+h8b5SEvQhH0fakTU+LwAKC88XLa9+E2pLb7b2WefTTzYc2nTpk0j8QerhFXwuUS5q7Qjg/2II44ggptLKYmnYPWQsSOBwIyAdqiKzPWs1+AlzEe4g+dFbaNR3pjjLAEOVW0Li9AsX5XsGdnaCqy1tsJ3oO5M2w68sTiP/hZ7XodseEprlIAQCtl2220x8Y488khUM/YFES5UGOlIrNFYmv0Jw6PZY489+D3//PPzRUr4WWsrA4daS0lI1GSLI+GkOo5aR0vaIuXSwtQTJkzgOIF99tmHw7C015bL4OEPwoeZHdXw5cxdwmorLAKiRDEwjG1ceJ0wfMg2pksnKysynRlsc8W2cLxkgoWFa6BmieWNNnpKaxRYkMfYuXNnspB4/9FWDIiOwNRSIxtLM2RAbLQ5xfdoK7owOaNp3AYO6GWOx01dhSbAmWIj358+gRLBVOqTQUPAyPVtQbLVtddei2vGUe577733Qw895PkUgI4t2gRhpMtAgIIk/6BH0ehVW2EtssgiABT77XrLLbdw6isOVJ0IYtqgKRJiWPQS4PeZxVNaYljREhAyffAKSQ4idKJmwUribhifGdkzeumll3QhCAHaBGXtKiXxmahOGhQWASl7EF4Vl8KCmLjbjTfeyEEo6pvAM/qGwopVjvbs0qIQWGaZZURh5fNhIH6E08HRSNGEPYZmj5aXHG3FG0svBWJEImnnX3ZwePnPOeccTwlatmyZ16lAqdIqkewSEF5mlJ2KrRJkxUlkp8xYWuxyCO0tvfTSSqFjVpCHTe2bCwdXKUnsyDRiwx500EEJLiGRuNVXX93FHm0ngs6PD6VBgwnGDxrZU1vBTjFNhomEJRQE6kwDaTg7EWiO9SD7WUvCFhsRWbwhWthJYROaN0f1EsrhD9yiRomdLK2SCg1L0Coq4fnnn0/QTbWQB6SWYyyNXtK7SJpVC1fEZCqhsNTfxx13HHke6u9YHIgK8eY3CpkM85JcjktI5UoGXmHJhoD9Gcs2TmauaruEaH3qYNknIsRD+RhRFb7w0Uf6IgPOdSOhiQRl9f3AfgrGl1FVn/zVgTNIWDch34fg9yqrrJI8iO5NllaR6RIQ7RjiynElDPmBrI6AncqcNJYGL2qIoBJWj95tYKOaGBb6DutsxowZOoAViwPaDUrPhTScjOfCGcSE5ygwbIgwvHI46YTPEvIbIOBhpZ5lWpD8RUhof8YKEt45bGZVVwlGO1nZyAwOcxXREhA8L/b1iPIYotpLg4ASPJtSMeJzsaOqBzFwKK2UxAU4R7uceeaZaP9+/fqRJs7qXJS0Y0WS6Uo8LoEmWxe2OSEb6qJS2Y3aqVjG3GueYmdxiVqQhAmfMZckObY3kdIcFyJkEpDYGX1RyWYiRuuiD6Q9WmBBiJ2Qpy2YvTRoqPKNuoSai41OzE/qeHWLgUNppST2QmhBZkwVhORv1sWJV2xlxFKqRgpFuaeLMGUCTeYu0OZQmmT22NqpWEbPmicCiGyPJE+qemNnsRlzl1BP4fqM2TIU0dLEFVYUMmJb1HNQiF8EjrmPiXfG5sDLL7/M/Qg4dGzhp05B6jYnT9pkHDTO641jggnDS27jwMZZsoKwx8y3hRAkSoq9ETUsWwokc8RqXgiIAHTr1o09BH8ZyMLzJPa8nyb363Nw2HniqUJ6isc4uUuoZHN9xlIlz4vgv6KwUFU777wzpRgq3pwXfMWNw+tKcR/nh+Q7hY0DwSDSUJNdsHxlsEfjPSRHgURQ1aXSu0jmtinJ2icwB73d5WrhwHX2eV29Rjsn2PTq1SuZmEdDWomhT2F0fRcSZQP25DE9FZaPeExUhITJ8pfWW/mguzM4N2dH5TKDibgffvjhnqvzJ7NxIL32mGOO8R+hCEp2CYhh6ZHxgtlS4KQqYy7yp6ht4qX1rLjCCiN/hWJD4nqeYrPnmHqDzn/k+hxPxEomawqnNZQMmUxXKAI4hsQciVIZs2Bw4diixNFWaC77B61E3hnVS2S9U4REUIx8F4ouSbzCwfSUOeF+Gn0bRbDX5+jbKBoooSfOmcn+KxZWZoCEsUwECLGx/UeVgpHKj8fBMXUoI350zoqnYP4HqNv30+y00056Fl0FlXA5DQYgqfnqBh3NGFvzZFRiklOGwiUFT3PZlZjJ4sGoyxhykdAT3pLJRGGVDLhMl4QAB5+S0qFOKI7SEZQZMGCAv+qJ8vbs2TNpykgf/mDyDTqKFu1Z//U5RiUmqurBBx/kIKMEUT3FY4RcJEyQpIFdorAaCL5MPQcCbImwJcqRKbRyFDLlVvqwKgJtJZzFGL3uIXqDDnlw0QIvu3YKxgzX59T6+F3iUcBg1Jw1SsJaV5SBXmJYGUATlvwReOCBB9j7o+yRkiPyMMhOtI/WU5doffHFF57Tk81AaognMWRRjRC9Qce4jaJRl9O4xENy4zaKRknoD3VmSlFYmaETxtwQoKKbOpuhQ4eSYEVGPsYUFVT26JRAcdNf7GV/BjEuJPaaSnG0x4ltSbifhi1LhuLAPMUY4PU5Rq1VQySMRTX3RnEJc4dUBqwZAc6i+OGHH1LZyN7mbuRUMgg4KoeYl3HvaTIjR4ZF6VXBpmKhhBMFSs0gZ29hAxLAQqtiCaoTJmDUwXK8M2N/ExbOhk09TIIcDnVmmUvIBPEUC2apuiSRf4uQ0CVYye1iYZUMuEyXHQH8O06toISFzFLu6cg+UI2cxLCN2yjYqRw9erTPMBh6PmluFNxEVaTPyAaNcRtF7hJmEKkIFrGwikBVxiwEARQWaegYLH369FFWDzczGzMRIOcywXynt2+j0JfTqPPFXNOVc31O7G0UQUnowidLe2k59TKRIFAnAmgHLknzLwzk8BnsjjondbGn1k6VU/Nk11ppgQOR0AVgtvbK35qTRUkLTwURIK+SxEjqcri6jT1E6mMI6yRbWBQAkxwfPca+gusWkedAQFxC+UBUAwEC2ypFiz1ELozhai8UFirJJT00pMXjOULGNp+LTNqrhYBYWNV6XiKtLwKoKs7jV2cq2CldvqMIXWAIiMIK7IGIOIKAIOBGQNIa3NhIjyAgCASGgCiswB6IiCMICAJuBERhubGRHkFAEAgMAVFYgT0QEUcQEATcCIjCcmMjPYKAIBAYAqKwAnsgIo4gIAi4ERCF5cZGegQBQSAwBERhBfZARBxBQBBwI/AvBB03dcbpmDoAAAAASUVORK5CYII=" /> </span></span><br />
<br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;">We choose the matching that minimize<span style="font-family: "times" , "times new roman" , serif;">s the total cost of this matching.</span> </span></span><br />
<br />
<br />
<span style="font-size: small;"><span style="font-family: "times" , "times new roman" , serif;"><br /></span></span></div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-60228908784827364202015-11-28T21:42:00.000-08:002015-11-28T21:42:12.524-08:00Reading 32 : $P Recognizer<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="gs_citr" id="gs_cit0" tabindex="0">
Citation: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Vatavu, Radu-Daniel, Lisa
Anthony, and Jacob O. Wobbrock. "Gestures as point clouds: a $ P
recognizer for user interface prototypes." <i>Proceedings of the 14th ACM international conference on Multimodal interaction</i>. ACM, 2012.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=2388732">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The $P algorithm is a gesture matching algorithm that follows in the family of $1 and $N algorithms. It is able to compare a candidate gesture with a predefined template, by treating the gestures as point clouds, while removing the timing information. This ensures that the algorithm is invariant to multi-stroke data.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The key approach in the algorithm is to match each point in the candidate to some point in the template. This matching is done by using a matching function. The goodness of the matching is defined using the follow equation:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAYIAAAA2CAIAAABFtAkJAAAAA3NCSVQICAjb4U/gAAAOJ0lEQVR4Xu2dd6wWxRbA6VUUUAIo8BRCUyGAoFKkKSVAKKJElEhEJKiJFEsUQQjSEjpIC70ohCKgoZcIKggINkRApUZBjR1pAu/9fJvs27e73+xs+fbud79z/yDc2bMzZ36ze/acM+Xm+Xdu/Nm0aVODBg1KlSo1YcKExPYvI5RMLD1RLDcRyEtn8siPEBACQiDnCOTLuaalZSEgBITAPwTEDMlzIASEQA4TEDOUwwMgzQsBISBmSJ4BISAEcpiAmKEcHgBpXggIATFD8gwIASGQwwTEDOXwAEjzQkAIFAiAgKVGb731Vv78+e+4447Dhw///fffjz76aIB65BYICEx5DIRAkOWLH330UdmyZRs2bLhs2bLmzZs3adJk27ZthQsXFpoBCAjMANDkllxGIEhQds8991y+fJndEtgg/oNbJDYo8GMhMAOjkxtzDYEgZihv3rw7d+5s27YtFLZs2dKoUaMPPvjg2rVruQZKnB0RmHHSlraSSSBIboieHDly5Mknn+Q/xYsXP3/+/JkzZ/LlC2LRkgklZq3SCvOXX35p0aJF9erVY+6UNJe1BMaNG1epUiVf3Q+SG/LVgAjnLIEFCxaULl26Y8eOOauGtC4EFATEhVHAyQ2XiJpbt26dG3oifci9BMQM5d6xzZPnzz//LFiwYJEiRXJzJ6VvmU9AzFDmj2HqHqxbt65du3apr8sVIZAIAmKGEjEMaVJi/fr1YobSxFaqjZCAx0zZDz/8wHz81atXb7jhBs5UdTbMIuCLFy/+/vvv/Gu92rlz50mTJjnls7kkZpjMYLKK4rrrrstm5ta+8xgvWrToypUr33zzDQ/zyy+/LGRCEogMqeeJtn379kVXZuB+/vlnhTBm6OTJk++++27v3r159FnQyFunkM/OS3HCfPvtt3nrspOza6/379//2GOPcQnrXKNGDdavu4pJoT6BqJD+s6dJ/cNHtXbt2lgiJn0ZP7WwcZVlRF26dBk+fLiOcFbJxAnziSee+PXXX2142XbDHsBsYM53kUW21p7y9JKzN0rYirR9+/aoOGQJ1ciRmtw8gjKsT9GiRZcvX37XXXe98847kydP7t+/v6cjV65cuRUrVjz33HNs9ShUqJApz3Pw4osvjh8/npIBAwZMnDjRWtX333/PwidekpIlS+LsEQzeeuut/PmK559/3rNFHYFu3brhoN17770suZwzZw7zR+zI5UU9cOBAsWLFaMhWiVpbnRadMhHCdFZuLYH8hQsXIGkt5MU7dOhQy5YtrYXpxq7W07zqd3Q8q8UfZ981E4WMuCHMgnUjRH3vvfcY/fvuu8+zEh2BxFJNONL/46b5QVi8eDFDwqDu3btX8xZ8orNnz1qFMTE9e/Y0Sgz32Ly6atUqNql99tlnZgmWokyZMkR5ms2pxfgMsuzb9OaqVq06evRo4xbe2GeeecZ5u0Jbp7CvkkhgqlskOT179myrDPk74mWbP5tu7GolzasBRkenZjqLS4g5tgrzjPXr1w+31LMGojastlossVSTidSEaePmHZSZd/bq1QtLdNttt/3222/qsUl1NdWLjcWpWbPmTz/9ZL2RVCJmyBlWpKpcXY53xrfRkME40hHTY6chvDDn7am0dUoGKAkPU91onz59fvzxR6vM4MGDN2zYYC2JAbtaSfNqgNHRrHn16tUjRowwhfft2zd16lTM07Fjx4gI1JXwtbARc8onlmoykZoAbdx8mKFz587dfvvtvMAPPfSQZpLINmyuL/bRo0dxld9//33nGOO/OAuDlVjzkeRucevM7yERL0+ns1pXbZ1iwUrCw1S0i+YPP/ywVYDxIhtCqGsWxoNdoaT1UoDR0az5r7/+ouOG8KlTp/713x/mW2688UZmVNSVeJqhJFNNJlIDuJObd27IDI9JqZAkInRauXLljBkzCGR0ImdPGVJIdevW5dAip+TQoUOdhcFKOE/DvPHDDz+sV68eaRqjhCRC/fr1g1Ub+K6oYGJNCDDJelg1wdFr2rSpteSLL75gitq6/TgMdtJJbFXjgBcyLGxYY/cskc7cuXNtaujDCTk6Cn3I+jG+GCBMT8WKFU+cOKGvladktFRpbubMmcePH69Tp0737t35dezYsfxLOtVTE6dASKQKTcIjdXLzt3yR4xbfeOMN+kyC+ZNPPnF23m8JMdfmzZuZVnO9kefGtTxkIWaocePGISvhdvypHj16PJLix0hFKVoJD5O3iyOfsES2VohEbEi//fZbwl5TLCT2pUuXsujmpZdeGjZsGC95rVq1Dh48qOipr0sBRketz8033/zpp5/60kFTOFqqdJxlBMxK85k3FCAxyjdGUxmFmF+knpqERGrjhuY+vCGjn+T8SHG/+eab5OGZYypRooSi/56XsP14aNY3xLzFOstGoMuMW6dOnTwr9BQgYclihxdeeMEpSXd27NiBhXVeci3hs7BkyRLXS5qFYWCSoWPuEn+EbLT1HA94Mjlwyy23WHXAX2ABqlkSBjsxLHtlcawIagh5OnToAAcmLjS7rBYLMDqe+jBvS5pM3a5xle8KOTVyhcavuE4YWfw+41ccWLL+Vo8yQqo0AUbDD2rWrBm/Xrp0iVyBa5Sg0xdTJgBST030kbqqauOGjG8zhONNRAYgPsIETRMmTHBtSbOQJDSSN910k1N+1KhRfGyNcjIdTgFKpk+fvmvXLtdLWEnX0y0+/vhjUieu3hCRGj+utaWpMAxM3hAWQ3JWERvHrKaTpADZEJvC2IsCBf431mGwY/hwf6h/9+7dROg8sqngxDM6nvpgPnilUylpLbd9V/jG8GQax/u53h4hVeonNYEdZDSNFS08qJUrV7a9GvEg9dREH6kON2R8myHuwQNiowbh61NPPeXajH5hhQoVWBz05Zdf2rIzRGqmpWBg+C49++yzzmrJT/lNUeFwMrqYc2tt5G6ZuibHwZS29XV1tmgt4aFhwsv8eNqEGar58+d7ngYXGKaR22rfvv2sWbOYnTXdUhLwTlY8zV9//bWpYUjsRj2YISMBQd6RqIdn10Yg5tFJpQ9wnLqpR1bzauRUSbGRQTc8WU40da5sig2pWpOQSG3coO0vN2QMD0q89tprvLeuwZTmEBpiuAO8RSzhwQQYJTzTRBmnT59u1aoVJXwT+HRz9j5TS75qTiVM+tbpLPDqPvDAA6D3lUTg44liRPKuPwsXLvS0QSgZEia5IWb9tm7datLDZLOowtZ9LC+RmlkYADsfA5Y1UAMB8oMPPojx3bhxY7Vq1ShZs2YNo5YKuK9yzdExldHRh+CRXIYvNTSFI6RqtMjn0HBUwct0kG2eQVMrm5gmUu6yUlVrEhKpjRtN+/aGAERO9umnn77//vuDcbHdRaKBmVEmblCOBBAPNG6wuS+cKIklHqwGDrlFE7ccXxd8vDzUyVoS/AjzI9m1a1dMBrkhwx+OpF86lYSHSUjCQPAAGTlpuuAaV7Ik/dVXX7Wq5Bc7NRP/klPD7SpfvjxZknnz5rHyiNQMv7o2qkPAkPE7OqYy3O6pD4n8NHlDEVI1ONx9991VqlRhluqPP/7go+j0htKHlJqtVNWahETq5OZj3RAGgvQnDv+gQYPUCy5SXQ22EocMFJ4XyeNU1UZSzuQRo26tKpi2+sqEhGk2RKoOQ2Cs5HrllVe++uorVx34ePD0uF5yLYwHu2vTzkLn6DhlXEs+//xzAm3XS56FOk9dtFTNtWxsLSJR7alhGAE1UoUmYZCaCtu4+QvK2FPGWufXX39d3yqHl7z++usJNHQCnDBtkTMKPyvhS4GoYOI5EnCxfoIxJmPNpK+rGvibxL+ul1wL48Hu2rSzMPDoMM9Fx50V6pQQe3qGRRFSZX+DkTTBBPCKhZz88eygAqlakzBITa1s3HwEZWvXriUJwtnGmhaBzRNkT/ye0e/EN3DgQGdhhCX4CCxQYvL78ccfj7BadVURwoQwU1ck1AhpWYuUql0yYqwnYlBS2SnbjenGnkpPW3mY0dmzZw/JeGNeT7M5v2IRUmXOgTkfJmfIQjAFFDLOVXTEE6lCk6iQ2rlp+nWkihlO2zYlxb2sVmD/OrkPqwx5L3LbRsmQIUMUt8d5iSk/ovGRI0cacY3ZdPq0jQSmFRGLCdlHzvoGUuwKdORx6KZtUBTySbiUanQ8deMJBEgMnc04qglBauWmlRsis8ukWKqkg/OBYIMYWSh2rzkvSUk6YAKcyS+yzjZLKrSFQEYQ8A7KSNqzfHnMmDH4t66z5qRy+fIw8cyCRtL7ZNdY8oBPaBxnoXAOs/BSmmDiCjGZyBrcwLu6snAspMsJIqA2lvi0bdq0CaAuZ2upa87Cq2mFye42Yr0spCpdzgUEPP5qKxu7gm0XIm8aPjkdwPwl+RaBmeTREd1ykICHGcpBzaRpISAEsoSAv3VDWQJFuikEhECcBLxT1IY2mkdtcAYIS8K/++4723H3cXYp+W0JzOSPkWgYJwFdM5TqqA2brmSmyYBEe8ZdnDjiaUtgxsNZWskUAlpBGTsnp02blildSrieAjPhAyTqxU/A2xsyjtpg3RB/24clQlOmTGGC0KYo25rYkhu/9hnXohUmZwawvVB4ZtwgisKRE/A2Q7ajNiI8pj7yziS/QhtMjqkXnskfNdEw3QS8zRAbWTkNk1OTOT/pzjvvJPfs9IY4kNj825jGfoJ0652h9Vthsnubw97UPAVmhg60qO2LgNa6IePMAcIuz6Mw2OfNwUDEGvyxaf40hf6Bqr6UzmhhgZnRwyfKp4OAlhlKR8NSpxAQAkLAIKA1UyawhIAQEALpIyBmKH1spWYhIAS0CIgZ0sIkQkJACKSPwH8Aly35Mt2OMIUAAAAASUVORK5CYII=" /> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The Hungarian algorithm is used to find the best matching, by treating this candidate-template point matching as an assignment problem. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The authors feel that this algorithm cannot be classified a $ family algorithm as it is fairly complex and requires us to solve an optimization problem. Some of the heuristics adopted by the authors are: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(1) Find all the Euclidean distances between points in C and T, and then sort thme, and choose the first n points that can yield a valid match.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(2) Use Greedy heuristics</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-35474434556223928762015-11-28T20:36:00.000-08:002015-11-28T20:36:24.128-08:00Reading 31: R Trees for Sketch Representations<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="gs_citr" id="gs_cit0" tabindex="0">
Citation:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Guttman, Antonin. <i>R-trees: a dynamic index structure for spatial searching</i>. Vol. 14. No. 2. ACM, 1984. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=602266">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The primary motivation behind this paper in the context of this project is to implement relative spatial indexing for sketches and shapes which have a well defined bounding box.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
R-Trees are used to spatially index objects that can be represented in an n-dimensional space using intervals in each dimension. In the simplest form, each object is represented by a rectangle, i.e bounding box.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
For most of our implementations, our sketches are well defined within a bounding box and can hence be spatially indexed to build a tree that gives us the relative position of a feature with respect to all the other feature objects that are present.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
We first construct an RTree using a standard dataset of geographical features. The parameters to the RTree restrict the maximum number of nodes and hence the split size and depth of the tree.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
To query the RTree, we query the RTree to find out which leaf node the given bounding box is in. If the candidate and template bounding box occur the same node of the RTree, then we say that their relative position is the same. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-64439793270012388692015-11-21T21:59:00.003-08:002015-11-21T22:04:59.021-08:00Reading 30 : Course of Action maps<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Hammond, Tracy Anne, et al. "A Sketch Recognition System for Recognizing Free-Hand Course of Action Diagrams." <i>IAAI</i>. 2010.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="https://www.aaai.org/ocs/index.php/IAAI/IAAI10/paper/viewFile/1581/2355">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Course of Action diagrams are used by military commanders to plan field operations, with various symbols used to represent troops, supplies, obstacles and movement patterns. An important aspect is the use of domain specific information to tune the recognition algorithm.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Initially, the grouping algorithm detemines which recognizer to send the strokes, PaleoSketch for geometric primitives, and a HWR for text and decision graphics. The segmentation is done by breaking every stroke into a series of lines, and then using Paleosketch.Primitive recognition is done using an extended version of PaleoSketch, which can be combined with LADDER to form more complex shapes. The system also recognizes dashed primitives, decision points (10-line stars), and handwriting. It also uses an improved version of LADDER, CALVIN which uses heuristics to account for confidence values of shape decisions. Some of the other recognised shapes are phase/boundary line, arrows , obstacles and decision graphics.</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-31138442066147111522015-11-21T21:53:00.000-08:002015-11-21T21:53:04.681-08:00Reading 29: Hand-Drawn Concept Maps<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="gs_citr" id="gs_cit0" tabindex="0">
Citation:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Jiang, Yingying, et al. "Structuring and manipulating hand-drawn concept maps." <i>Proceedings of the 14th international conference on Intelligent user interfaces</i>. ACM, 2009.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://zhang.ist.psu.edu/pdf/p457-jiang.pdf">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Concept maps are extensively used in visualization. Also, anything drawn by a person on a map is a mental map of some sort. This paper presents a way of recognizing these concept maps on a hand drawn sketch. We believe some of these recognition concepts can also be used in drawings on maps.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The stages in this approach are preprocessing, partitioning the graph into subgraphs, extracting the block of each subgraph using dynamic programming, and finally generating the concept map's structure.The authors also created a set of intelligent gestures that could be used to directly modify the extracted figures. The paper looks similar to the multi-stroke paper in its graph-based approach of merging strokes.</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-21255854029790806392015-11-21T21:45:00.000-08:002015-11-21T21:45:42.921-08:00Reading 28 : Sketch-Based Spatiotemporal Visualization<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Godwin, Alex, and John Stasko. "Drawing Data on Maps: Sketch-Based Spatiotemporal Visualization."</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://www.cc.gatech.edu/~stasko/papers/infovis15-poster-sketch.pdf">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper is a joint effort by GeorgiaTech and the Atlanta Police Department, to help create visualization tools for understanding crime patterns, based on the user interaction with a map surface. The system allows sketching of 3 types of paths - shortest path, user defined path and radial path. The main purpose of this paper is to present a technique of visualization aid using map sketching. There is little or no recognition component used here.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<br />
Discussion:<br />
The map is constructed using two underlying datasets - spatial events and traversable roads. The paths can be queried either using shortest path, a user-defined path, or a radial path where a user is shown all the possible traversable locations within a particular radius. The rendering of paths is dependent on the spatial characteristics of the path segments, i.e in this case, spatial regions are characterized by the number of crimes recorded. The user also has the power to create visualization summaries by sketching out regions on the map <br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-14307487683852230572015-11-14T18:09:00.000-08:002015-11-14T18:09:50.006-08:00Reading 27 : Visual Symbolic Recognizer<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-size: small;"><span style="font-family: inherit;">Citation:</span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">Tom
Y. Ouyang and Randall Davis. 2009. A visual approach to sketched symbol
recognition. In Proceedings of the 21st international jont conference
on Artifical intelligence (IJCAI'09), Hiroaki Kitano (Ed.). Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA, 1463-1468.</span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"><a href="http://dspace.mit.edu/openaccess-disseminate/1721.1/71572">Publication Link</a> </span></span></span></span><br />
<br />
<br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">Summary:</span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">The main approach followed in this paper is to represent symbols as feature images rather than temporally ordered points or geometric primitives. There are four feature images concerned with orientation, and 1 concerned with endpoint. The feature images are first extracted from the input and then there are stages of smoothing, down-sampling and classification.</span></span></span></span><br />
<br />
<br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">Discussion:</span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"><br /></span></span></span></span>
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">The online stroke sequences are converted into low level feature images.</span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"> </span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">In the smoothing and downsampling phases, we try to increase the tolerance to local shifts and distortions by applying a Gaussian smoothing function. We then downsample the images by a factor of 2 using a MAX filter.</span></span></span></span><br />
<br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">The symbol recognition is done using a deformable template matching algorithm. The IDM allows every point in the input image to shift within a 3x3 local window to find the perfect match. To compute the IDM distance, the following equation is used in the paper.</span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"></span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAcgAAABNCAIAAACtyWNiAAAVyUlEQVR4nO2d0U8bV7rA5w+YFz/yYAnJssQDUhShPICiK3gAJULCUStkkUSWiYpslEQ2QdghwoCKTVQmamK0rdNNR22stHW6jHp3nW6dLG6Du4Js46pGYGXdFHpNaqfAmmIZC8OYM/dhbDB4DDP22NjZ7/foOMz4zJnfnPOd73yDMQAAAICoYMd9AgAAAG8aIFYAAACRAbECAACIDIgVAABAZECsAAAAIgNiBQAAEBkQKwAAgMiAWAEAAEQGxAoAACAyIFYAAACRAbECAACIDIgVAABAZECsAAAAIgNiBQAAEBkQKwAAgMiAWAEAAEQGxAoAACAyIFYAAACRAbECAACIDIgVAABAZECsAAAAIgNiBQAAEBkQKwAAgMiAWAEAAESmcsSanLOdlmCi8ZbNv3HcPwkAgDeTyhErsxmkdPKUFuu01CLN638lVgM/eZ97XJTdZulTNab/AIbXmqfjRT5jAAD+OylArGjd/9CsM4yMmbqaG8+bHs7FkHjnxX3EsPt6Y0qM8m7HQh5iTMaCzyYs5+UYhkl0zmV+cgYAoGJBsbmHg9cM5lGTprWxfeihf73YomIKEOt22PnudWeQZhiGQdsBUoGf7HT8vC3emXGC1r63NElTY862j+Y382uiZMzv0DfWnrP/vCPyCQIAUE6gJWfviDOUYBiGYeIB8jye55hMGHmLNeTU1ODn7AusmdCvDmU11kIGii6qZMz3QRvOqlXaTDyL5vn0QXTIqT/zvjdegqdXnqDgwy5LZrxiK+jot8z8Ie5B6PDkaPeHz2PwiDl21p5bDaPuV5UwjSpxtzmsZbJuk/2frDg1ePXuEAotOZRYVQv5otjnnSnWyIz1supiax2OYVhVXet5VYrzrXVVeF2H6cHzFXpXQ/Sqd4J89CI1/Ucv7QppScTKMEzs36QqvYzVNOhZyVeN2yFqoN+9LKpZk2vTY024tMny/VrBf3cnQLYa3NG9DzYDpMbgXj34PfTKNdSVvnAYXtd6UaW+4ggkeRwCRZ8R53qp4Gah5yoi0X+a66swDMOw0+aZ9eM+mwKJTJtb2GFAtXkmceTX6aCz5x3ieaQUT/vK6ja5WybrNtn/CVr2fmZ/FEhN/9GiXVFysTIMwzBJn/UkjlX1u6OZh06Epz9QyaubBp+E6eyfxoYC6rqdSyUa/tGLlLYupdaavvQ4vxzYCjou4RiGdziCJRMrC+0lZBiGa6kw7xEPCrl6FKW7agJYnzGfxiS9rgif27zMQYkZSzV2Quf6nde3l7/pOX3dVbLof+V0m1wtc4RY98GGAnqc4WLHLLPEihbtCgzDFPbFg822HaK6JRiHPVHMd1fZqCZni754lXFMOuTU17BDAVyupYIcuj8m6NXAsx/8qyK4XpBYUxdOwKQBxb23GhRkYFvkpkMrzz57FChoMLPzgmyp4uqEJQf9PvOZK5BnKJ9lM0C2Y9gF+yLPLhEPkBcbLNP5xriEUT7dhgfcLcNbrMnY3D1lbRc5fwyLV8mIq1eCSU7b5jiGChGXTnJwLIZis2TnBZPz5xJalSW55hk5lU4RUJLz5TSbFQchYmUvHH6CeM7X6ChIddZ3OMR3F+0lZCoqXMBfQGFKjefohCWG9hIyjYDRXDYoSKnl2Gmbn/ePQSGqU9pNhYo+qiqrbsPr4Fwtw0+sydj8p52KYedCaR5YB8Ua8ZjqMaze5IlwfJedNWRO0OhFqqcv9QTY+dV55+8lnR6gyHNCkVrHwtvHfX8c+/hGXISIlb1wdTkDBVmgoKNDImQCyJuCxcre7Tk6YYkpXKwRl06CSU0eAdtRUJBSnyqJvMqo2/A8fHbL8BArooNf9XTfn48lGYbZCX5959H/Fbtt94uV3d2UK7bFihVL9zP61eSgUmG6N0FRFEVRn5s7elylvhU2Z21t1Sm1No1Nr4k3xIm4dKkFMg0V/NVN9OhMo2adoq7tPXc4gWKzD4xXDebRAVVjvfqD6ZVUP0v6bafZ/5QyC+sI9pOJYNhNdOtNY+/qWk+3GqkjJ5gCxMpeOAGRMjpMaXHOCSBan7cb1frBAbWy2z4b237lvjVgeq9PqTBPhnkNa/IQK4q9dN3RKtT9Y2ajnvj8ft8pkQKsydj8A6O+X9f29uDk7poy2gw49J0fevmsaOchVhRdcN3pVFwaGBsx6G9/df+alHeANc1mgGzH1VS42Hd/2XQbFJv9xNg3rHurJXMVZ/PFF/qr4961jC9ytMxRYkV0+MlgW4eJ/JKiKIqa+Nzc1SPscuTDPrGiJYeSO8DKMAybuLA7Yl17TqSznlIcy9wNbS84OuXsiUhOXf9H3ikCXMQDZAeGtXTpb37FLoCiRUeHDG/Vm67/+Xk0yTAME58210r2beJiEyQyzUK/INuk2JlL+uG/srFgFHR04LIjhyT8xZq6cALmmxGPqZ5rGLUZpAa6ydkYYtCyU1vVckVn+iSwsRn4Qnuqmuf1FSpWFJsl1Q3pdVE2lJ+7EwoBLbtu9D8K0TEv0ZjROFEv0Zy1PJsDoWJF6/NkV03TCGsTFKI6JZiQAGvqr2x4hqTVlplEcc1aLt0GhVw3LM5QgvYSMkxh87M3E0p4iRMHR9McLXOEWGPPiHTme5rdQxSRTLHuRN39VTkDLuzipqDLkPGnF+zn9ms4JzXDHj49fo/8trrygQ5TGgyrarbNpYM6MS/RiGEn9a7X6Qu7RKlk+9tkiVLJ9omV/SSzOgHtJWSYRHfEAJ+3WNkLJ2i+uUSp5CetvgNXEkUmr1/4JLUukZgxV2MSrXMZJRbsF3G81TK9yudGFyZWtDptacVrBtzp8elOgGwR5yGdWLD3E951dilsb22AXRlTOniFrYSJlU22azDu5vCxxxJ+yyR91pNYYSGIoymXbrOz8FkX8UOcXeXDLzmCWwzDpBf9Oh1L+yKq2S0jJCugdGSKNeolmnMHXOJ+mwLDJPXED2W3xV6Era6csGLNzKZkxZp5sZcolQyTEd69C51DrJmPWTaocpR9eIuVvXBC5ptJn/WkXEUtHThg1G2+4vwtlfG35FBiUoX9pdBRkxCxsol6kgbrT1t759BfJU6Adc375ZOFbbQTIFuwvfmBsJUxQWLd9pOKaqxh3LeVbrOo21AlMMDKEqZU2Bmrr6h1gsqk2+zEvH97tBA/+PzLteiX1TJlL1b26Zor4LL1k7VBguHnyUDZeZURbavrAVixNhLeWPoTVqyZdxpvsWZ+R1yxshcue76JYkverz/UnFEfvBPYE5Bl3SH7/vOGZ0h6ZIr+zs/2c9W8JiLcPeePGXMjhjWa97aTRb1Es6gZrJsBsj2jLgT7uzjFnViwX+Q3rapWkP6sNXsUnxmt3Vfch53MCg2wMgzD6iOz4+0/0orbolYdidriPiwyxtltDi8AIla34TydANmC1WrTgmY2PCYp1zMpq2XKXqxsCJU7oy0ZcQ/UYJJTg08L31BUHHa3ukpz7GLIg8oQKwpTajwrRBPzOW7Z7F9ZNVKuO+HoO4Sdl111rggWnIARK3tvZ2pU9AxWNiy+lyMY99sUAsQtYMTKTl0zNSo0gzWDQ8UqClzd5qgCIEXsNltBxyV8Lw7ArgNzPZMqTazsoybHtCX+o7VZWsiyezFjrOkfEPsX0SSVqz9lkyrEoCLEmrpwVZw9KdedgF7aFTWHztdCTk1NfnuUBYiVbYeMo2TM09e89x/x2l95OFG3oSpj4s8uLfIXtwCxsn2jndzdG7E3md2JeSe+ErJnAi3aFfkZmfcRuLrNUQVAithtVt2GugzLJxbtFzifSdktU+ZiZUOoXI8I+tXk4FlJeqGzTKGXXMZGXOSTrAixshdOrqa49tDmHGKEnJqafWd9gAMTsa1Zm+Y+z7tFgFgPZlAkI66+VIB1wzPYRYURw6B1v2NQozcZVO8QU95/jPYZ372iHv4uY5KbWPU/9wZz7FAJUypsrwXQslMrwbOXXw79MTzFyrpg78so4tKnAqwRz2A/FaYZ+pX71sCNq2+1pEpJoLhvvOUsmf38oL2ELK/pAm84u82RBUAK6TaIXn3xLOd12n/XoN+c2lqM6zplt0x5i5VtxIMBl1hw5ovBtlq56oPpcrYqWp+7e1Ei19gD4k6dKkGsqQuXMVDa9wtyiTXutykOnsCm364+idUMe6LbEfdADVatdPyKGIZh4gsPLTenXgsY5PFdvNoOUd2SE4Q3gdicU4OyRY61k4GNqOe9LsciYlDcd/fyuDeG2BFWg9EdDFJX5Blz+dRkSJJjq9LWT9aG6lTRjdSOEgH58IIWr1CI6pQ0E94owyZmGi6clUtbyBfJ6NRQ18MgSkbct4bdrzc8Q9KUMuJ+m4Jr+JxccV7F80q/4cvh3YZhchQAKaDbpMLxNZ2cIwAm5rO2piWejD6/3YxzTsI4WqZMxboTdPard2vcyBvbL6Zj3283ymqaNJb73/5S8u2qgkiEnH01+Nkh3nc+L9Y8hPp8a10VhuGyxrdVVxwvXjiuqN5ulOFs6S818d0vntvqVMPJG9tVVxz+1d1P8LrWi0ZHYGPt4Hd+euEwqtobZRj7HS3hWcl1CoeKFW35H1xW7b9wasK9sl8BOcWK4jOjtdIhz0ZGm23/4ryukMnb+wau9Yx/88M3NxWt2hHipklvHJ/6jX/ij7B0K/q3KaKzTTM0ZrrWM/40HF+aHHy7TdevN34R2EQM88fMrTvuSDK11UI65NnYocM/PvHuqQ6Fv+45VYVhNRpniOsAydj8A23zecPYiEF7VfN2jbCCI8LSrRLhqdsdbdqRMZO+58Op8Hp4cqSl7eqwfvBBIMYwG4HH7sBmZMbclFrgQi/tChlXfkLEY2oozhsu+HWbnAVACug26NU3Pf+DYxiucXL2eBSbtWsVSoPFbLh6TaOo4p6EcbRMmYr1WI9eOOzDrRQ1tkuPsOpWnByy2hCdMtW0WX3iL48UXiuAi4jHVH9I5i/tHddxizUD9NKukAorPFb4ltYDxKfNtQ2pnISISyfhyk/Y+sna0GwWufCuAA4rAFJgt6G9hI5brBkkFu0XMhJaM+BqGRCr6CA6SGnl1aIUPy1DiitWZt1LnC3GsCjps9blGJUU8EfnbKdlqWWT7cVvnxyYwW4GSFP2rDa1p4t4FmOY9NxWYAHfpM9apxMx1pn0206nQoRowzMk5QikovjMaG39rWMrwX5EAZCCus1O4FNNdi3U1Ha191Nls7f9pELOlYDE3TIgVpFBa99bmqrLq2agqBRZrAyKTBpPXC5JFaV8if9oba49Zw8k/HebU8HuRMg50ru/diVaezp87atQVi+gvYQMk7JiRbFZUn2mtMUtOUj6bafZqTRa8Qw2cSygoyDVedYocv113vAoAJJ/t0ErnuFhjv9IewkZhrNiRevzpKaeM7cnR8uAWEVl029Xn8TbPvDln1yVjLiGdneM5CCxSF1vravCCtu4vbNI9bTW4QITpwsS607Q/SeCGNE04ri8vW+MsDp82VNLesU91KJ3hsr2ybT9cqK7uUnTpzf++W+fX29X3xgz9V5/sF+OKPT45jh3Nsjmv6nBawbzGGHuValukOWwWoBeTw2dVxpGTLqORpkka/s4vezqbxG55AV/eBYAya/b0MuPrTcnOV+vEgtQFp1hhCBG+lSXjOR3ixw3dc6WAbGKB/1qcvAsXtC7AxAd/sZ4eoBHJY4jons8D7fhGZIK3FAkwoj16PNanyd7u497HPdfQyLsferdq89yhvBmPmiTsfn73enqdmVNqbvNYS0DYhUJtD5PdsklF+/O5V0JPBlbcJqaqnmFijKje/mTK7HmMFDs5++9mesmyVjgX17R895QdOHJ5Cy8TLAErDg1bAITveQynmka+m7/+OuPWdfThfK3KktJu81hLZN1m3B8UnoqTqyJ8ORIE95odC3l1XCIXp1//HFPI45hWCufxU205FAWXg4D/epQygTkpQNvJOi155bBYB4d0HQZyWmRNl4D5UhliTUZm7unlJwUsgSRjC3Neb3TbueE3Tba135qL4TUfNef6709dGjaplNqh8aMvTf6Oqp41u48SCI8/ZFWeXlkrF9/49rFKiF56QAAVDIVJNbMFwgWzt6rxrOO83pqqK2ezfZAvzm1tXnVcqdXpixN9SOetSTD0MtOnURQXjoAAJVM5YiV3T4sFpzpxwzDMCjuvVW/+6/opV0hz+ct5PEfiPqadA3QxKL9Qn4FTQAAqEQqR6wlIuIx1e+tMuXaG3ME7Mb23cILv7t0J/KpdgwAQGUCYj3AEqWSVZtnEgyTkSP1H9//epZ2krH5v1gstvuETjtiHjTf7GtWWn2cSR10mNLspb5ueEzSEzpXOOZ7/O1SgqFfucdvmnXKS9SvOwyzE5x458KDBRjMAsAbBIj1ADGftTUlVjro1NdjLWQgNj3a+2h5Z/Hh8MMFGu0EyBbpkCe26BwmnIu7+VqJsPtOt/HLwCZiGLTlG29IiTURcvbVYO1kIDwzanYub8dnbDc9v3iJthbyxQ5Dhymt9Lhz7gAAEBcQ60FQbJbUqnTmdw36sYm/f9zdfL7XYP5sryBhMuLqlXLsF4j6rOfw3cQstD5P6pW6YbOhzzLx1/vdCmWvcfAzf2o3e3zaXKskA5sMs+o2NHGXUgUAoGIBsfJm+xfnMOEMhj2mRoX9JWI2Fx4QDxYy0/XRhufePT5v1g1TKrY8655hAQB4cwCx8ib+o7VF0ffeoNE8pNPftt99z+LY/6o1FJn5031eRYm2X05c7jTeI29rmyUHqlsCAFD5gFjFIrk2fffm4+wSS4dALzt7GszTRXxjHAAAxwGItfREfda3ajV3/mL/wEJQ/krZGw4AAG8qVKzJmP+hUXNtxNDZQUzO/eN9vfGGVj02lfWGCYZBdNh9y2i82tZumV5FDMMwUZ9VeZZ8AT4DAKBIVKZY4z+OX/7IF0syGx6TFK8xTv4nOHFJfpLjFbNo2T18yx1Z8ZgaUjVQxKlWBQAAkJNKFCuKz3z4LltIfHdnFB32PvmRo1zQ1s+Pvw5sxqfNtU3sq3LQol2BKWx81u4BAADyohLFugvP6tGZr5bcfdknDFgBACgWFS3WzOrR8cVvnwY2OXUZ99sU6ZfuRjym+lwv4AUAABCFShRr1Gc9JzlnX0jM2ZqrZISXZhAdenS91xlGDLtaRXQPOvb2SsX9NgVbAwWtPR08VZ1PtSoAAADeVKJY4wsTPfVNXTf0po//9mlP+zumMZP++ufp9+GguG+8Gcczy/Wjle+GFBcM75l0ykYZ1kx4YWs+AABFpBLFyoON72/fS79dcm9daztEdUuO8Y3tAAD8d/BGijUZnfnko9T7L5Mrzqu4vMcZ3qLD3xjr24amXoNWAQAoKm+gWNHaP9+/+WQ5rU+0MnVLbzSP3dCob5AzIXg7CgAAxeYNFCsAAMDxAmIFAAAQGRArAACAyIBYAQAAROb/AZop9ydw8Lg0AAAAAElFTkSuQmCC" /> </span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;"> </span></span></span></span><br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="color: #222222;"><span style="line-height: 16px;">The system also incorporates two optimization schemes in the form of coarse candidate pruning (using the distance between these reduced feature sets), and hierarchical clustering (which uses a branch and bound technique, where clusters are first formed using agglomerative clustering).</span></span></span></span></div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-61979118217723581192015-11-14T17:34:00.003-08:002015-11-14T17:34:55.302-08:00Reading 26 : Shape Context<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: inherit;"><span style="font-size: small;">Citation:</span></span><br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;">Oltmans, Michael. </span><i style="background-color: white; color: #222222; line-height: 16.12px;">Envisioning sketch recognition: a local feature based approach to recognizing informal sketches</i><span style="background-color: white; color: #222222; line-height: 16.12px;">. Diss. Massachusetts Institute of Technology, 2007.</span></span></span><br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;"><a href="http://rationale.csail.mit.edu/publications/Oltmans2007Envisioning.pdf">Publication Link</a> </span></span></span><br />
<br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;">Summary:</span></span></span><br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;">This paper focuses on recognizing sketches based on their visual appearance rather than stroke information. However, comparing pixels based on perceptual similarity will lead to inaccurate results. Hence, the sketches are represented as parts, and these parts are compared. The main challenges in this include over-tracing, variations in signals, as well as segmentation issues.</span></span></span><br />
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;"><br /></span></span></span>
<span style="font-family: inherit;"><span style="font-size: small;"><span style="background-color: white; color: #222222; line-height: 16.12px;">Discussion:</span></span></span><br />
<div>
<span style="font-family: inherit;"><span style="font-size: small;">
The main takeaway from this paper is the bullseye representation used for images. In this representation shapes are described as collections of visual parts and</span></span><span style="font-family: inherit;"><span style="font-size: small;"> their allowable conceptual variations. A
visual part represents the appearance of a region of the shape. In contrast to a conventional tile based matching system, a bullseye representation is selected. Each of the subdivisions of the circular region is a histogram
bin that measures how many pixels of ink are contained in that
region. A part is represented as a vector formed from the counts in
each bin. To form the representation, we compute first calculate the visual
parts at a sampling of locations that cover the sketched symbol. Then a
standard codebook of parts is used to identify each individual part.
This codebook is preprocessed for common parts in the domain(eg.
resistors). Finally, the representation of the sketched symbol is
calculated as a vector of distances that indicates the degree to which
each of the codebook parts appears in the sketched symbol.</span></span><span style="font-family: inherit;"> </span>The match vector representation is used to train a classifer to learn
the differences between shape classes and to learn the allowable
variations within a shape class. </div>
<br />
The second task is to localize of shapes in complete sketches, which is done by identifying candidate locations and training the classifier on them. <br />
<span style="font-family: inherit;"><span style="font-size: small;"> </span></span></div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-11263580073057125042015-11-07T23:50:00.001-08:002015-11-07T23:50:19.222-08:00Reading 25: User identification using pressure and tilt data<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Eoff, Brian David, and
Tracy Hammond. "Who dotted that'i'?: context free user differentiation
through pressure and tilt pen data." <i>Proceedings of Graphics Interface 2009</i>. Canadian Information Processing Society, 2009.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary;</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Along with the usual parameters used in understanding a sketch, this paper reviews other information that can be used to unique identify a sketcher. This paper investigates how the physical mechanics of a pen alone including pressure, tilt and speed can be used to unique identify a user. Some of the major use cases for such a system include forensics, identify personal traits to build trends for education, and also for collaboration on online whiteboards.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The data is collected in Cintiq, which provides values for tilt and pressure. This application records the following information about the users strokes, the coordinates, at what time the pen was in contact with the surface, at what angle and using how much pressure.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
2 experiments were performed:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Exp1:To determine how consistent a user is in the drawing.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Exp2: To determine if we can build a classifier to find the creator of a sketch </div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-7114879191200927712015-11-07T23:31:00.001-08:002015-11-07T23:31:32.195-08:00Reading 24 : SketchRead<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Alvarado, Christine, and Randall Davis. "SketchREAD: a multi-domain sketch recognition engine." <i>Proceedings of the 17th annual ACM symposium on User interface software and technology</i>. ACM, 2004.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=1029637">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The aim of this system is to create a universal system that can be used to recognize sketches across multiple domains. A major constraint is such systems is the trade off between accurate recognition and freedom of drawing style. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:<br />
Most previous systems make use of assumptions or limitations on the drawing style to improve recognition which in turn interferes with the user's liberty of design. Some of the challenges the author discusses are incremental nature of sketching ,messiness and segmentation of strokes into shapes.</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-72666180073391184292015-11-07T23:22:00.004-08:002015-11-07T23:22:59.546-08:00Reading 23 : Tutorial on HMMs<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Rabiner, Lawrence R. "A tutorial on hidden Markov models and selected applications in speech recognition." <i>Proceedings of the IEEE</i> 77.2 (1989): 257-286.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://www.robots.ox.ac.uk:5000/~vgg/rg/papers/hmm.pdf">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper is a landmark article on Hidden Markov Models, and is cited by most scientists who use HMMs, and it presents a comprehensive review on HMMs an their applications. The core aspects include the construction of a basic Marov model, additional parameters required to construct a Hidden Markov Model, along with forward and backward chaining algorithms. The paper also deals with the three main problems that are solved using HMMs.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:<br />The paper begin with explaining probability primitives and basic Markov models. It then discusses the characterization of the basic parameters required to build a HMM, i..e No. of states, No. of observation, apriori probability, transitional probability and emission probability. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The 3 main uses of the HMM are :</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
1. Given an observation sequence and a model, what is the probability of that observation sequence? (likelihood of those events occurring)</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
2. Given a set of observations and a model, what is the most likely sequence of states under which the observations hold?</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
3. How can the model parameters be adjusted to increase likelihood of a desired observation.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The paper the delves into the application of the Viterbi algorithm for forward and backward chaining. The math details are avoided in this post. </div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-7946837890484275062015-11-07T23:12:00.003-08:002015-11-07T23:12:57.012-08:00Reading 22 : HMM-based efficient sketch recognition<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Sezgin, Tevfik Metin, and Randall Davis. "HMM-based efficient sketch recognition." <i>Proceedings of the 10th international conference on Intelligent user interfaces</i>. ACM, 2005. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=1040899">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper deals with the application of HMMs to sketch recognition, that is treating sketches a series of incremental states built upon every stage of interaction. The goal is to capture variations in drawing style for various figures, and break these down into a sequence of observations that can be used to build a probabilistic model.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The core details of HMMs are discussed in the next paper.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper primarily deals with the two phases of recognition using a HMM:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(1) Encoding: In this stage, strokes are converted to geometric primitives.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(2)Segmentation and Recogntion: We need to have identified object classes apriori, and constructed HMMs for them. Individual object recognition is done using forward chaining. To recognize in an overall scene,we end up with an optimization of problem of assigning models to subsequences such that there is maximum likelihood of some scene.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-41188376905031332802015-10-24T23:22:00.003-07:002015-10-24T23:22:36.753-07:00Reading 21 : Ladder<div dir="ltr" style="text-align: left;" trbidi="on">
Citation: <br />
Hammond, Tracy, and Randall Davis. "LADDER, a sketching language for user interface developers." <i>Computers & Graphics</i> 29.4 (2005): 518-532.<br />
<a href="http://www.sciencedirect.com/science/article/pii/S0097849305000865">Publication Link</a><br />
<br />
Summary:<br />
LADDER is a high level language that allows developers to write sketch definitions for complex shapes, that are comprised of primitives. The language can be used to model the components of a shape, and enforce some constraints on how these components are position with respect to each other. Other important features the languages allows are editing and display commands, which determine how a shape should react when edited, or how it should be displayed upon recognition.<br />
<br />
Discussion:<br />
The shape definition comprises of components, constraints, aliases, and editing and display behaviours. Shapes can be defined using shape groups, hierarchical shapes and abstract shapes. There is also an additional constraint available that allows recognition to be orientation specific.<br />
<br />
Two import rules used are:<br />
1. Jess Rule - All possible combinations of shapes are checked<br />
2. Constraint Satisfaction Rule - The systems tries to satisfy all the given constraints while moving the points as less as possible<br />
<br />
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-87683620402473716372015-10-24T22:16:00.000-07:002015-10-24T22:40:32.546-07:00Reading 20: Recognizig multi-stroke primitives<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Hammond, Tracy, and Brandon Paulson. "Recognizing sketched multistroke primitives." <i>ACM Transactions on Interactive Intelligent Systems (TiiS)</i> 1.1 (2011): 4</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=2030369">Publication Link</a></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Most research in primitive recognition often assumes that a basic shape such as lines and polygons are are drawn with a single stroke. If multi strokes are allowed, the user is forced to draw under certain set of limitations. This paper seeks to eliminate, by giving the user full independence to complete one shape in multiple strokes, or multiple shapes in a single stroke. The main stages in this multi stroke recognition system are, graph building, identification of strongly connected components, merging components and removing false positives.<br />
<br />
Discussion:<br />
<br />
By analyzing the sketches of a set of users over a range of shapes, it was found that there were a lot differences in the styles of drawing, especially as far as number of strokes in a shape are concerned. Many people tend to make use of touch up strokes and continuity strokes, even while drawing a simple figure.<br />
<br />
1. Use the stroke information to form a graph. The endpoints of strokes form th nodes, while an edge between two nodes occurs if either of the three conditions are satisifed:<br />
-There is a stroke between the two points<br />
- The gap between the two points is within a threshold of the average stroke length of the strokes passing through the end point<br />
- The gap is smaller than the average width of the bounding box of the two strokes.<br />
<br />
2. Tarjan's algorithm is used to extract the strongly connected components in this graph.<br />
<br />
3. The merging of nodes identified done in the same component is done by removing peaks at the end points, and finding the point in the two strokes closest to each other, and creating a touch up stroke between them.<br />
<br />
4. The final step is remove false positives. <br />
<br />
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-46707697982396954772015-10-24T21:54:00.001-07:002015-10-24T21:54:09.196-07:00Reading 19 : Sketch Recognition using Sounds<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Li, Wenzhe, and Tracy Anne Hammond. "Recognizing text through sound alone." <i>Twenty-Fifth AAAI Conference on Artificial Intelligence</i>. 2011.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3791">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper makes use of the classical idea of capturing the sound information while making strokes, to recognize the stroke. The sound analysis is performed using multiple features extracted from the input signal of the sound. The stages in this recognition system are noise removal, feature extraction, template matching and dynamic time warping.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
1. End Point Noise Removal:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Two techniques are used to remove end point noise. In the first technique, first the environmental noise is obtained as the signal energy for noise amplitudes over the first 150ms, after which the amplitudes are sample at every 45 ms, and checked against a threshold multiplied by the environmental noise, to determine the start and end points. The second method assumes the first 20ms as environmental noise and uses it to calculate a Gaussian probability. Every 10ms segments is checked, and marked as silent or valid. Finally, all the valid segments are merged. The mean amplitud value is used to normalize the signal.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br />2. Feature Extraction. Two main features are extracted, mean amplitude for each time frame, and mel-frequency cepstral coefficients.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
3. Template matching: This is done using dynamic time warping. The DTW constraints defined are end point constraints, local continuity constraints, global path constraint and axis orientation.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-85513007377560279842015-10-18T08:37:00.003-07:002015-10-18T08:37:44.998-07:00Reading 18: Geometric Basics<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />Dr. Tracy Hammond<br />
<br />
Summary:<br />This handout primarily covers some of the geometric basics required to have a good understanding of sketch recognition systems.<br />
<br />
This includes fundemental trignometric rules, linear algebra, vector algebra.</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-69987654346685736942015-10-18T08:36:00.000-07:002015-10-18T09:03:56.088-07:00Reading 17 : PaleoSketch<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Paulson, Brandon, and Tracy Hammond. "PaleoSketch: accurate primitive sketch recognition and beautification." <i>Proceedings of the 13th international conference on Intelligent user interfaces</i>. ACM, 2008.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=1378775">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Paleosketch is one of the landmark techniques used for primitive shape recognition, i.e after early processing of corners is completed. Many current applications make use of Paleosketch as the technique to obtain individual shapes before passing it to higher level recognizers to obtain further groupings.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The pre-processing involves a few stages, such as computing corners (Using a three step process of selecting consecutive corners, merging similar corners in a neighborhood and finally selecting the highest curvature point in a neighborhood as the corner), plotting direction, curvature and speed graphs and using them to compute NDDE and DCR. We also detect closed shapes, overtracing and tails at this time.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Next, the strokes are passed to a series of shape detectors. Each shape detector subjects the stroke to a set of geometric constraints, returns the shape if all the constraints are passed. If the stroke does not pass any test, it is recursively broken down at the point of highest curvature. Later, the detector also tries to recombine primitive shapes by passing it to a secondary function (as dividing at point of highest curvature may not necessarily give individual shapes all the time)</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The geometric tests are designed for the following shapes:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
1. Line</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
2. Polyline</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
3. Circle</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
4. Ellipse</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
5. Curve</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
6. Spiral</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
7. Helix</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(Refer paper for the exact details of these geometric constraints)</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br />Finally, to select the final set of shapes the defines a stroke, a hierarchical ordering is used that tries to minimize the number of lines returned (i.e it favors arcs over lines, and complex shapes over heavily segmented polylines)</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-86776350811420537932015-10-18T08:34:00.000-07:002015-10-18T08:34:54.042-07:00Reading 16 : Combining Corner Detectors<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Wolin, Aaron, Martin Field, and Tracy Hammond. "Combining corners from multiple segmenters." <i>Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling</i>. ACM, 2011.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=2021185">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:<br />
This paper aims to consolidate all the previous attempts in the domain of corner-detection, and integrate all these algorithms to build a powerful corner detector. The accuracy of this detector was proven to surpass that of any individual detector. However, running this corner finding algorithm on the entire set of points proved to fail drastically, as there are sharp spikes in the error metric which prevent effective thresholding.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The first step is to run each of the 5 corner detectors individually, (Sezgin, Yu and Cai, ShortStraw, Douglas-Pecker, and Kim and Kim), and the union of all the obtained corners is taken, with duplicates removed.<br />
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Next, the a Sequential Backward Floating Selecion(SBFS) technique is used to remove corners one by one from this combined set. At every iteration, a removed corner can be added back if its found that the error decreases. The corner to be removed is determined as the one that causes the least error upon removal.<br />
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The error metric used in this case is Mean Squared Error, which is the mean distance between every point and the vertically closest point on the polyline formed by the remaining corners. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The corner removing stops when there a sharp spike in M.S.E (an elbow in the curve), whose slope exceeds that of a threshold. The remianing set of corners are returned as the final output.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
To determine the threshold, we use a training set where the corners are already labeled. Next, the we take the medians of the slope before the elbow, and the slope after the elbow for these shapes, and construct the Gaussian distribution for the 2 sets. The points where the probability of these two models are the same, is taken as the confusion point, i.e the threshold.<br />
<br />
<br />
<br />
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-36594703115002425552015-10-11T15:58:00.002-07:002015-10-11T15:58:32.649-07:00Reading 15 : IStraw<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<div class="gs_citr" id="gs_cit0" tabindex="0">
Xiong, Yiyan, and Joseph J. LaViola Jr. "Revisiting ShortStraw: improving corner finding in sketch-based interfaces." <i>Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling</i>. ACM, 2009.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<a href="http://dl.acm.org/citation.cfm?id=1572759">Publication Link</a> </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
This paper first reviews the Shortstraw algorithm, and then identifies its limitations and suggestions improvements. It also introduces curve detection, and provides experimental proof for the massive improvement obtained.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
We mainly need to discuss the 6 limitations that occur in ShortStraw, and how iStraw overcomes them.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
1. Initial Straws</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Problem : Straw fails to compute the straw for the first 3 and last 3 points, which can turn out to miss corners in some cases. </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Solution : iStraw introduces formalae to compute the straws for these points too.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
2. Timing information</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Problem : Shortstraw does not make any use of the stroke speed, which can actually be helpful in finding corners </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Solution. Use speed maxima to identify corners.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
3. Consecutive False Corners Avoidance</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Problem: Shortstraw tends to delete some true corners, after which the colinearity test fails drastically.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Solution: Use a two-pass co-linearity test, with second Dpass having more relaxed thresholds.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
4. Dynamic Threshold</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Problem : Shortstraw does not take into account the length of line segments, while determining corners. This is an important distinguishing factor is some cases.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Solution : In the second pass of colinearity test, a dynamic threshold based on length of the segment, is introduced.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
5. Impact of Sharp noise</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br />6. iStraw introduces curve detection by treating every prospective corner as a point where two rays coverage, both originating from a fixed shift distance from the point in question. For a line, the angle formed a this point remains fairly constant, while it changes drastically for a curve. </div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-57031575117059377312015-10-11T15:28:00.001-07:002015-10-11T15:28:39.158-07:00Reading 14 : ShortStraw for Corner Detection<div dir="ltr" style="text-align: left;" trbidi="on">
Citation: <br />
Wolin, Aaron, Brian Eoff, and Tracy Hammond. "ShortStraw: A Simple and Effective Corner Finder for Polylines." <i>SBM</i>. 2008.<br />
<br />
Publication Link: <a href="http://www.researchgate.net/profile/Tracy_Hammond/publication/220772398_ShortStraw_A_Simple_and_Effective_Corner_Finder_for_Polylines/links/0deec529f76e58d523000000.pdf">http://www.researchgate.net/profile/Tracy_Hammond/publication/220772398_ShortStraw_A_Simple_and_Effective_Corner_Finder_for_Polylines/links/0deec529f76e58d523000000.pdf</a><br />
<br />
<br />
Summary:<br />
This paper presents an alternative algorithm for corner detection, where the earlier work has been done by Sezgin, Yu and Cai. The main phases of this algorithm are Resampling, Bottom up Phase and Top Down Phase. The overall result was a massive improvement over the previous two techniques, in both corner accuracy as well as all-or-nothing accuracy. The biggest drawback of this algorithm however, is its failure to detect obtuse corners.<br />
<br />
Discussion:<br />
The main takeaways here are the 3 phases of the Shortstraw algorithm:<br />
<br />
1. Resampling<br />
The first step is to obtain a resampled representation by using an interspacing distance.<br />
<br />
2. Bottom-up<br />
<br />
A straw for a point is computed as the distance between the endpoints of a window containing the point.(window size is generally 3 on either side of the point). The points having short straw length are determined as corners, using a threshold of of (median * 0.95)<br />
<br />
3. Top-Down<br />
(i) First, it checks to see if every segment between two consecutive corners passes a line test (chord distance/path distance)<br />
<br />
(ii) Removing false negatives: If any two corners fail the line test, it is assumed that there must a missing corner, approximately between them, and the threshold is relaxed to find it.<br />
<br />
(ii)Removing false poistives: Checking for co-linearity among triplets of consecutive corners. <br />
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-1208720336475711312015-10-11T14:55:00.002-07:002015-10-11T14:55:12.779-07:00Reading 13 : Domain Independant Sketch Recognition<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="gs_citr" id="gs_cit0" tabindex="0">
Citation: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Yu, Bo, and Shijie Cai. "A domain-independent system for sketch recognition." <i>Proceedings
of the 1st international conference on Computer graphics and
interactive techniques in Australasia and South East Asia</i>. ACM, 2003.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Publication Link : http://dl.acm.org/citation.cfm?id=604499</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Summary:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
The main approach used in this paper is to combine primitive shape recognition with the early processing (as opposed to having a separate pre-processing stage as with Sezgin). The vertex detection phase is an implicit part of the stroke detection. The paper then explains its line segment approximation and curve approximation algorithms, along with some of the post processing features. The concept used for determining the fit of strokes against primitives is called 'feature area verification'.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Discussion:<br />The main takeaways from this paper are the approaches to detect lines, circles, arcs and curves.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Line Segment Approximation:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Try to fit a best fit line, and compute the feature area using this candidate line. The stroke area is taken to the length of the stroke into its thickness. If the ratio of the feature area to stroke area is less then 1, the stroke is recorded as a line</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Circle Approximation: </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Check if the direction graph of the stroke can be approximated as a circle. If so, take a candidate circle that takes the center of the stroke's bounding box, with radius as mean of distances between the center and the stroke point. Feature area is then applied to try to fit the circle. If the direction graph extends beyond 2pi, then it is checked for over-tracing and helical strokes.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Arc Approximation:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
1. Check if direction curve can be approx. using line</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
2. Find the perpendicular bisector of arc, and find the find the circle on which the end points, and this intersection points lie.</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
3. Follow the same procedure as for circles</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br />Handling Self-Intersection Strokes:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Uses two heuristics and compares results </div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(i)Simple is better</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
(ii) Specific is better</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
<br /></div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
Finally, the paper also covers some of the post processing routines, including:</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
-Elimination of false and redundant elements introduced by noise</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
-Adjust layout of elements</div>
<div class="gs_citr" id="gs_cit0" tabindex="0">
-Basic object recognition</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-48666217755367459342015-09-26T14:20:00.001-07:002015-09-26T14:20:25.858-07:00Reading 12 : Early Processing for Sketch Understanding<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">Citation:</span><br />
<span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;"><br /></span>
<span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">Sezgin, Tevfik Metin, and Randall Davis. "Early processing in sketch understanding." </span><i style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">Unpublished Master’s Thesis, Massachusetts Institute of Technology</i><span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;"> (2001).</span><br />
<span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;"><br /></span>
<a href="http://rationale.csail.mit.edu/publications/Sezgin2001Sketchbased.pdf">Publication Link</a><br />
<br />
<br />
Summary:<br />
<br />
The main aim of this paper is to deal with the low level stages in understanding a freehand sketch that does not restrict the user. It mainly deals with the use of curvature in the neighbourhood of a segment, as well as pen speed to identify corners. It also describes the user Bezier cures to model the curves detected in a sketch<br />
<br />
Discussion:<br />
<br />
The three stages in the pre-processing of a stroke are :<br />
<br />
1. Stroke Approxmiation<br />
<br />
(i) Vertex Detection<br />
<br />
While plotting the arc against direction, it is observed the maximum curvature, and minimum speed occurs at the vertices. Thresholds determined by average based filtering are used prevent occurrence of too many false positives. A combination of speed and curvature data helps eliminate the shortcoming of either.<br />
<br />
Generating Hybrid Fits:<br />
The initial hybrid fit is the intersection of Fd and Fs. The candidate list Fd is computed based on scaled magnitude of curvature in a local neighborhood around the point. Successive hybrid fits are done by performing a kind of merge sort on the remaining members of Fd and Fs, using the orthogonal distance squared. The final set of vertices are the selected by choosing the fewest number of vertices that also have an error below a threshold.<br />
<br />
(ii) Handling Curves<br />
The ratio between arc length and Euclidean distance is used to approximate the distance. Curvature is represented using a Bezier curve. But since fitting a Berzie curve would require solving a 6th degree polynomial equation, we resort to using piece linear curves with error metrics. If the curve still cannot be fit with minimal error, it is subdivided into smaller curves.<br />
<br />
<br />
2. Beautification<br />
Mainly consist of smoothing of slopes using a clustering approach<br />
<br />
3. Object recognition is done using hand tailored templates that examine various simple properties.<br />
<br />
The system was evaluated by users drawn from a diverse background, who found the system impressive, and highly accurate in terms of beautifying and understanding their diagrams.<br />
<br />
<br /></div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0tag:blogger.com,1999:blog-1026870631599197919.post-25873496955234457072015-09-26T13:16:00.000-07:002015-09-26T13:16:23.707-07:00Reading 11 : Combining geometric and gesture-based features<div dir="ltr" style="text-align: left;" trbidi="on">
Citation:<br />
<span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">Paulson, Brandon, et al. "What!?! no Rubine features?: using geometric-based features to produce normalized confidence values for sketch recognition." </span><i style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">HCC Workshop: Sketch Tools for Diagramming</i><span style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px; line-height: 17.9111px;">. 2008.</span><br />
<br />
<a href="http://dl.acm.org/citation.cfm?id=1378775">Publication Link</a><div>
<br /></div>
<div>
<br /></div>
<div>
Summary:</div>
<div>
The main aim of this paper is to investigate a combination of geometric features (how it looks), and gesture based techniques to build a highly accurate classifier, and produce normalized confidence values. The authors than proceed to finally establish how gesture based features turn out to be insignificant when an optimal set of features is computed using a greedy algorithm to maximize accuracy. </div>
<div>
<br /></div>
<div>
<br /></div>
<div>
Discussion:</div>
<div>
Geometric based recognisers focus on determining the error between a sketched shape and its ideal version using a series of geometric tests and formulas. A total of 44 features were selected for evaluation (31 geometric, 13 Rubine's), and a dataset consisted of 90 samples each from 20 users was aggregated.</div>
<div>
<br /></div>
<div>
The relevant features are determined using a greedy, sequential forward selection algorithm. Optimal features are the ones that that yield highest accuracy during the SFS (Subset feature selection) process. Using a 50-50 split (same as PaleoSketch), the quadratic classifier was found to perform poorly when the entire set of features was used. When a an optimal set of features (obtained thorough multi-fold validation) was used, the quadratic classifier was able to match Paleosketch. </div>
<div>
<br /></div>
<div>
The advantages of this system over Paleosketch is that it is easier to code, and is computationally faster since it makes of an optimal subset of features. Since the data is partitioned userwise, the subset selection algorithm tends to bias towards user independence, and most gesture-based features were found to be insignificant.</div>
</div>
Girish Khttp://www.blogger.com/profile/02686780908580630988noreply@blogger.com0