Find pattern in image - Teh Forum

<body> <div id="header"> <span class="left"> <span class="back"><a href="lthread_list.php?webtag=DEFAULT"><span class="image mobile_back" title="Back"></span></a></span> <span class="image mobile_logo" title="Beehive Forum Logo"></span> </span> <ul> <li> <a class="reply_all" href="lpost.php?webtag=DEFAULT&reply_to=42326.0&return_msg=42326.1"> <span class="image mobile_reply_all"></span><span class="text">Reply to All</span> </a> </li> <li> <a class="navigation" href="#"> <span class="image mobile_navigation"></span><span class="text">Show messages</span> </a> </li> <li> <a class="main" href="#"><span class="image mobile_menu" title="Menu"></span> </a> </li> </ul> </div> <div class="menu main"> <ul> <li><a href="lthread_list.php?webtag=DEFAULT">Messages</a></li> <li><a href="lpm.php?webtag=DEFAULT">Inbox</a></li> <li><a href="lsearch.php?webtag=DEFAULT">Search</a></li> <li><a href="llogon.php?webtag=DEFAULT">Login</a></li> </ul> </div> <div class="menu navigation"><a href="lmessages.php?webtag=DEFAULT&msg=42326.1">1–10</a><a href="lmessages.php?webtag=DEFAULT&msg=42326.11">11–20</a><a href="lmessages.php?webtag=DEFAULT&msg=42326.21">21–22</a></div> <div id="page_content"> <h3 class="thread_title"><a href="index.php?webtag=DEFAULT&amp;msg=42326.1">Find pattern in image</a> </h3> <div id="messages" data-navigation="42326_1_22_10"> <a name="a42326_1"></a><div class="message" id="message_42326_1"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">16 Mar 2019 00:50</span> <div class="clearer"></div> </div><div class="message_to">To: ALL<span class="message_count">1 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.1">42326.1</a></div> <div class="message_body"> Anyone here clever with image processing? I'm working on a project which is using OpenCV to match a template (120 square or circle points - it's an eye test chart) and find it in another image, then translate that so the new image points line up to the template.<br /> <br /> I'm using OpenCV's feature detection (in Java) to match the template. Only problem is (and I've only just discovered this) it doesn't work with images that aren't based off the template. It's picking up the shape of the points which are all slightly different. If I change then all to perfect squares or circles it breaks.<br /> <br /> I asked a question on Stack Overflow and had a reply that there is no easy way to find the pattern in another image and need to make my own algorithm, but no idea where to start.<br /> <br /> I can use contour detection to get the location of the points, then somehow need to process them to match up to the template. Does anyone have any idea how to do that? </div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.1&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.1"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_2"></a><div class="message" id="message_42326_2"> <div class="message_header"> <div class="message_from"> From: Peter (BOUGHTONP)<span class="message_time">16 Mar 2019 14:50</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 16 Mar 2019 15:24"></span></span> <span class="message_count">2 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.2">42326.2</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_1" target="_self">42326.1</a></div> <div class="message_body"> I haven't done this sort of processing, and I don't understand your second paragraph, but your final paragraph sounds like it might just be geometry/trigonometry? <p>Can you post an example of the starting point and the goal, and what you've got so far?</p></div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.2&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.2"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_3"></a><div class="message" id="message_42326_3"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">16 Mar 2019 15:39</span> <div class="clearer"></div> </div><div class="message_to">To: Peter (BOUGHTONP) <span><span class="image post_read" title="Read: 16 Mar 2019 15:56"></span></span> <span class="message_count">3 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.3">42326.3</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_2" target="_self">42326.2</a></div> <div class="message_body"> I have images like this (squiggly lines added to test template matching):<br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=b13cb1c53ec76180c7de05a84b0d2e12&filename=2.png" style="width:400px;height:258px;" /><br /><br /> And I was using this as the template:<br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=2b5d5dcda18c67803198677b72567ff8&filename=temp.png" style="width:400px;height:225px;" /><br /><br /> OpenCV has feature detection which can detect features in one image and map it to features found in another image. This works great using that template with the top image as the template is extracted from the source image. It detects the shape of each point in the template and finds them in the source image. I've been the same images from the start and assumed it was working properly until this week.<br /><br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=edb7b891b0c408b4556bd5d20a81e50a&filename=good_matches+%281%29.png" style="width:400px;height:139px;" /><br /><br /> This can then be used with affineWarp to align the first image so the positions of each point line up in the same place as the template. If I use a different image the points don't match up properly and I get this:<br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=567c9cbc5822e14665b7c3b54fdea06f&filename=good_matches.png" style="width:400px;height:217px;" /><br /><br /> So now I am trying something much more complicated and manual. Currently got as far as this - threshold image, detect contours, filter depending on size:<br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=d743275ae51cef3313cebceac1fec876&filename=countours.png" style="width:400px;height:404px;" /><br /><br /> Nearly all the points are picked out as contours, but I need to find known points that I can match up to the template for the alignment.<div class="edit_text">EDITED: 16 Mar 2019 15:40 by CHRISSS</div> </div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.3&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.3"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_4"></a><div class="message" id="message_42326_4"> <div class="message_header"> <div class="message_from"> From: Peter (BOUGHTONP)<span class="message_time">16 Mar 2019 16:52</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 16 Mar 2019 16:52"></span></span> <span class="message_count">4 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.4">42326.4</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_3" target="_self">42326.3</a></div> <div class="message_body"> Ok, I think I understand the issue now. <p>My (possibly naive) approach would be to extract coordinates of all dot positions from the template and work out the ratios from the centerpoint, e.g. the top two dots are 1 unit high and 0.836 to either side, the bottom outer dots are 1.62 and 1.11 units away from centre, and so on. </p><p>I'm assuming the axes are consistently present, so you can do edge detection and/or a separate template to detect where the centre point is - otherwise I'd probably start by looking in the cleanest corner (bottom left) and trying each dot found until enough of them match to identify where the centre would be. </p><p>Once you've got an anchor point (the centre) and have identified enough dots that match the template ratios, you can calculate how many pixels are in a unit and resize appropriately. </p><p>Dunno if that's the best approach, and it's also assuming OpenCV can actually extract the coords of dots, but seems reasonable enough?</p></div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.4&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.4"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_5"></a><div class="message" id="message_42326_5"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">16 Mar 2019 18:49</span> <div class="clearer"></div> </div><div class="message_to">To: Peter (BOUGHTONP) <span><span class="image post_read" title="Read: 16 Mar 2019 20:52"></span></span> <span class="message_count">5 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.5">42326.5</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_4" target="_self">42326.4</a></div> <div class="message_body"> Well this is a project for work but I'm also using it for my dissertation. For work, apparently no, they don't always have the axis. For my dissertation I can make them all have it.<br /> <br /> If I can work out the center of the chart bit it might be easier. Although you have given me an idea which might work. Start from each end of the list of points (yeah center coordinates are easy) and try and find a point at known distance/angle from them. Only problem is if the image is scaled more in one direction. I don't really know how similar they will be. <br /> <br /> Thanks for the ideas. 4 months to sort it out.</div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.5&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.5"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_6"></a><div class="message" id="message_42326_6"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">16 Mar 2019 19:35</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 16 Mar 2019 19:35"></span></span> <span class="message_count">6 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.6">42326.6</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_5" target="_self">42326.5</a></div> <div class="message_body"> I tried to do something with 3 nested for loops. The contour detection picked up 1,000 points. So (in the voice of Dr. Evil) 1 billion combinations. And got an out of memory error </div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.6&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.6"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_7"></a><div class="message" id="message_42326_7"> <div class="message_header"> <div class="message_from"> From: Peter (BOUGHTONP)<span class="message_time">16 Mar 2019 21:45</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 16 Mar 2019 21:46"></span></span> <span class="message_count">7 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.7">42326.7</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_6" target="_self">42326.6</a></div> <div class="message_body"> There aren't a million points in your contoured image, unless perhaps you're counting individual pixels? <p>Even so, a million pairs of numbers shouldn't use more than ~32MB, so you may be creating unnecessary variables and/or need to scope things so the GC knows when it can throw them away. (I just checked and the image you posted only has 0.61 million pixels in total, including the blacks, so something isn't right.) </p><p>Actually, the dots in your image are ~7px in size, and the gaps are bigger - you can resize down to ~100px wide without merging them, which means you can fit coords into a byte or two (so 1-2MB of memory for a million), and at the same time simplify the threshold/contour/filter process. </p><p>For the angle/scaling issue, you can use the axes - the ends should be at the same x/y - if they're not it needs rotating. Without axes... well assuming the squares are supposed to be square, you can probably still get OpenCV to detect rotation/skewing and do the appropriate calculations/transformation.</p><div class="edit_text">EDITED: 16 Mar 2019 21:46 by BOUGHTONP</div> </div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.7&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.7"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_8"></a><div class="message" id="message_42326_8"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">17 Mar 2019 00:52</span> <div class="clearer"></div> </div><div class="message_to">To: Peter (BOUGHTONP) <span><span class="image post_read" title="Read: 17 Mar 2019 19:47"></span></span> <span class="message_count">8 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.8">42326.8</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_7" target="_self">42326.7</a></div> <div class="message_body"> No, not 1,000,000 points in the image, only 1,000. Some are overlapping. A bit more filtering to get rid of them bright it down to 250ish.<br /> <br /> But when it was 1000, iterating over all 1000 inside a loop that iterates over all 1000 inside a loop that iterates over all 1000... that is a billion right? Extremely inefficient way to try and find 4 corners on the chart.<br /> <br /> Yeah I might focus on the axis for now. And if the width and height are always the same that could give me exactly what I want. <br /> <br /> I don't think the detection of the shapes is good enough at that size. Besides, not always any squares on an image.</div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.8&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.8"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_9"></a><div class="message" id="message_42326_9"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">17 Mar 2019 01:14</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 17 Mar 2019 01:14"></span></span> <span class="message_count">9 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.9">42326.9</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_8" target="_self">42326.8</a></div> <div class="message_body"> Or possibly Fourier transform.<br /><br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=ce9c7902365ebb8ef622fa7b982a4ebd&filename=fourier.png" style="width:400px;height:418px;" /></div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.9&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.9"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div><a name="a42326_10"></a><div class="message" id="message_42326_10"> <div class="message_header"> <div class="message_from"> From: Chris (CHRISSS)<span class="message_time">17 Mar 2019 01:20</span> <div class="clearer"></div> </div><div class="message_to">To: Chris (CHRISSS) <span><span class="image post_read" title="Read: 17 Mar 2019 01:20"></span></span> <span class="message_count">10 of 22</span><div class="clearer"></div> </div> </div> <div class="message_links"> <a href="lmessages.php?webtag=DEFAULT&msg=42326.10">42326.10</a> In reply to <a href="lmessages.php?webtag=DEFAULT&msg=42326.1#a42326_9" target="_self">42326.9</a></div> <div class="message_body"> Or maybe not. I thought that found the center but doesn't look like it.<br /><br /><img alt="" src="https://www.tehforum.co.uk/forum/get_attachment.php?webtag=DEFAULT&hash=a7e671cc466e6a610546d91a1fa775e2&filename=fourier2.png" style="width:400px;height:398px;" /></div> <div class="message_footer"> <div class="message_footer_links"><a href="lpost.php?webtag=DEFAULT&reply_to=42326.10&return_msg=42326.1" class="reply"><span class="image post"></span>Reply</a></div> <div class="message_vote_form" data-msg="42326.10"> <span class="rating">0/0</span> <span class="image vote vote_down vote_down_off" title="Vote Down"></span> <span class="image vote vote_up vote_up_off" title="Vote Up"></span> </div> </div> </div></div> <div class="message_page_footer"> <ul> <li class="right_col"><form accept-charset="utf-8" method="get" action="lmessages.php" target="_self"><input type="hidden" name="webtag" id="webtag" class="bhinputtext" value="DEFAULT" dir="ltr" /><input type="hidden" name="msg" id="msg" class="bhinputtext" value="42326.11" dir="ltr" /><input type="submit" name="submit" id="keep_reading" value="Keep reading…" class="button" /></form></li> </ul> </div> </div> </body>