Position detection of a defined mark in a picture

0
votes

I am still a beginner in coding. I am currently working on a program in C/C++ that is determining pixel position of a defined mark (which is a black circle with white surroundings) in a photo.
I made a mask from the mark and a vector, which contains mask's every pixel value as it's elements (using Magick++ I summed values for Red, Green and Blue). Vector contains aprox. 10 000 values since the mask is 100x100px. I also used threshold functions for simplifying the image.

Than I made a grid, that is doing the same for the picture, where I want to find the coordinates of the mark. It is basically a loop, that is going throught the image and when the program knows pixel values in the grid it immediately compares them with the mask. Main idea is to find lowest difference between the mask and one of the grid positions.

The problem is however that this procedure of evaluating all grids position takes huge amount of time (e.g. the image has 1920x1080px so more than 2 million vectors containing 10 000 values). I decided to cycle the grid not every pixel but for example every 10th column and row, and than for the best corellation from this procedure I selected area where I used every pixel loop. But, this still takes lot of time.

I would like to ask you, if there is some way of improving this method for better (faster) results or this whole idea is not time efficient and I should use different approach.

Thanks for every advice!

Edit: The program will be used for processing multiple images and on all of them the size will be same. This is the picture after threshold, the mark is the big black dot. Image

2
c++image-processingpositioncomputer-visionmagick++
Please clarify if the mark has a specific position or may be at any position. Moreover clarifiy if it has a specific size of may have any size. Also if the mark completely overwrites on the photo what is under it. – George Kourtis
Did you try to use algirithms like circle hough transform? It could limit your areas of iterest making your aproach faster. – Vinicius Zaramella
I guess you should read something about state of the art template matching. it's similar to what you do but pretty fast. – Piglet
Please also clarify if the image is completely digital and the mark is sure that will have white and black color ( that meaning 0,0,0 and 255,255,255 if the representation is RGB with 8 bits depth). – George Kourtis
use a GPU. they're built for this kind of thing. – Richard Hodges

2 Answers

1
votes

The idea that I find interesting is a pyramidal scheme - or progressive refinement: you find the spot at a lower size image then search only a small rectangle in the larger image.

If you reduce your image by 2 in each dimension then you would reduce the time by 4 plus some search effort in the larger image.

This has some problems: the reduction will affect accuracy I expect. You might miss the spot.

You have to cut the sample (template) by the same so you create a half-size template in this case. As you half half half... the template will get blurred into the surrounding objects so it will not be possible to have a valid template; for half size once I guess the dot has a couple of pixels around it.

0
votes

As you haven't specified a tool or OS, I will choose ImageMagick which is installed on most Linux distros and is available for OSX and Windows. I am just using it at the command-line here but there are C, C++, Python, Perl, PHP, Ruby, Java and .Net bindings available.

I would use a "Connect Components Analysis" or "Blob Analysis" like this:

convert image.png -negate                            \
   -define connected-components:area-threshold=1200  \
   -define connected-components:verbose=true         \
   -connected-components 8 -auto-level result.png

I have inverted your image with -negate because in morphological operations, the foreground is usually white rather than black. I have excluded blobs smaller than 1200 pixels because your circles seem to have a radius of 22 pixels which makes for an area of 1520 pixels (Pi * 22^2).

That gives this output, which means 7 blobs - one per line - with the bounding box and area of each:

Objects (id: bounding-box centroid area mean-color):
  0: 1358x1032+0+0 640.8,517.0 1296947 gray(0)
  3: 341x350+1017+287 1206.5,468.9 90143 gray(255)
  106: 64x424+848+608 892.2,829.3 6854 gray(255)
  95: 38x101+44+565 61.5,619.1 2619 gray(255)
  49: 17x145+1341+379 1350.3,446.7 2063 gray(0)
  64: 43x43+843+443 864.2,464.1 1451 gray(255)
  86: 225x11+358+546 484.7,551.9 1379 gray(255)

Note that, as your circle is 42x42 pixels you will be looking for a blob that is square-ish and close to that size - so I am looking at the second to last line. I can draw that in in red on your original image like this:

convert image.png -fill none -stroke red -draw "rectangle 843,443 886,486" result.png

enter image description here

Also, note that as you are looking for a circle, you would expect the area to be pi * r^2 or around 1500 pixels and you can check that in the penultimate column of the output.

That runs in 0.4 seconds on a reasonable spec iMac. Note that you could divide the image into 4 and run each quarter in parallel to speed things up. So, if you do something like this:

#!/bin/bash
# Split image into 4 (maybe should allow 23 pixels overlap)
convert image.png -crop 1x4@ tile-%02d.mpc

# Do Blob Analysis on 4 strips in parallel
for f in tile-*mpc; do
   convert $f -negate \
      -define connected-components:area-threshold=1200 \
      -define connected-components:verbose=true        \
      -connected-components 8 info: &
done
# Wait for all 4 to finish
wait

That runs in around 0.14 seconds.