{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T04:37:40Z","timestamp":1648874260698},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Image Grap."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p> We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) \u03b4 &gt; 0, find the largest subset B \u2282 P and a similarity transformation T (translation, rotation and scale) such that h(T(B),Q) &lt; \u03b4, where h(.,.) is the directional Hausdorff distance. This problem stems from real world applications, where \u03b4 is determined by the practical uncertainty in the position of the points (pixels). We reduce the problem to finding the depth (maximally covered point) of an arrangement of polytopes in transformation space. The depth is the cardinality of B, and the polytopes that cover the deepest point correspond to the points in B. We present an algorithm that approximates the maximum depth with high probability, thus getting a large enough common point set in P and Q. <\/jats:p><jats:p> The algorithm is implemented in the GPU framework, thus it is very fast in practice. We present experimental results and compare their runtime with those of an algorithm running on the CPU. <\/jats:p>","DOI":"10.1142\/s0219467809003459","type":"journal-article","created":{"date-parts":[[2009,4,30]],"date-time":"2009-04-30T06:22:22Z","timestamp":1241072542000},"page":"287-298","source":"Crossref","is-referenced-by-count":0,"title":["A GPU-BASED ALGORITHM FOR APPROXIMATELY FINDING THE LARGEST COMMON POINT SET IN THE PLANE UNDER SIMILARITY TRANSFORMATION"],"prefix":"10.1142","volume":"09","author":[{"given":"DROR","family":"AIGER","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben Gurion University, Be'er Sheva, Israel"},{"name":"Orbotech LTD, Yavne, Israel"}]},{"given":"KLARA","family":"KEDEM","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben Gurion University, Be'er Sheva, Israel"},{"name":"Computer Science Department, Cornell University, Ithaca, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00047-X"},{"key":"rf3","first-page":"298","author":"Choi V.","journal-title":"LATIN"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.09.003"},{"key":"rf6","volume-title":"Model Based Image Matching Using Location","author":"Baird H. S.","year":"1985"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00032-1"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00033-9"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/34.761267"}],"container-title":["International Journal of Image and Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219467809003459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T10:29:44Z","timestamp":1565173784000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219467809003459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":9,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1142\/S0219467809003459"],"URL":"https:\/\/doi.org\/10.1142\/s0219467809003459","relation":{},"ISSN":["0219-4678","1793-6756"],"issn-type":[{"value":"0219-4678","type":"print"},{"value":"1793-6756","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]}}}