Understanding centroid

[tmelorc]

I am trying to understand how IM computes centroid of a binary image.

Consider this simple binary image created with

Code: Select all

convert -size 100x200 xc:black -fill white  -draw "rectangle 0,0 79,49"   -draw "rectangle 0,50 19,99"     foo.png

From IM connect components we get

Code: Select all

convert foo.png -define connected-components:verbose=true -connected-components 4 null:
Objects (id: bounding-box centroid area mean-color):
  1: 100x200+0+0 54.8,121.2 15000 gray(0)
  0: 80x100+0+0 33.5,34.5 5000 gray(255)

My aim is to discover how to obtain the centroid of 0 component: 33.5,34.5.

My idea was: consider each white pixel as a vector v_t=(x_t,y_t). So we have N=5000 vectors, ie, t=1...N. Then, compute sum of x_t and divide by N. The same for y_t.

But what are coordinates x_t? I think that we have to split in two rectangles, for example, x_t=0..79 and y_t=0..49. Similar arguments for the other rectangular part.

But I'm no able to obtain the same value for centroid. I got 34,25.

What am I missing?

Also, using OpenCV pca_analysis I got 31,41 and the following image:

[fmw42]

For any given region (white or black), the centroid is just the average location of all pixels in the region. See https://en.wikipedia.org/wiki/Centroid

The difference may be due to the 4-connected option vs the 8-connected option.

Try

Code: Select all

convert foo.png -define connected-components:verbose=true -connected-components 8 null:

Sorry, but I do not know what OpenCV is doing to get that result.

[fmw42]

See also https://en.wikipedia.org/wiki/Connected ... t_labeling regarding 4 or 8 connected pixels

[fmw42]

Please always provide your IM version and platform when asking questions.

If you post your original image without the arrow and circle, I can double check the values

[tmelorc]

For any given region (white or black), the centroid is just the average location of all pixels in the region. See https://en.wikipedia.org/wiki/Centroid

The difference may be due to the 4-connected option vs the 8-connected option.

Try

Code: Select all

convert foo.png -define connected-components:verbose=true -connected-components 8 null:

Sorry, but I do not know what OpenCV is doing to get that result.

Thanks for link. This is very useful: https://en.wikipedia.org/wiki/Centroid# ... ped_object

Also, with 4 or 8 the result is the same.

[tmelorc]

Please always provide your IM version and platform when asking questions.

If you post your original image without the arrow and circle, I can double check the values

The original image:


My OS: Linux Mint 18 with

Code: Select all

Version: ImageMagick 7.0.4-2 Q16 x86_64 2017-01-02 http://www.imagemagick.org
Copyright: © 1999-2017 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenMP 
Delegates (built-in): bzlib freetype jng jpeg lzma png x zlib

[fmw42]

Also, with 4 or 8 the result is the same.

That is likely due to the fact that there are only vertical and horizontal edges and no diagonals.

[fmw42]

I get your same values with IM 6.9.8.3 Q16 and IM 7.0.5.4 Q16.

[tmelorc]

I get your same values with IM 6.9.8.3 Q16 and IM 7.0.5.4 Q16.

Thanks for your effort.

I decided to use a very simple L-shaped image to be able to compute by hand and compare. But maybe I'm misunderstanding some computations.

If I'm not wrong the top left corner of image has coordinate (0,0) not (1,1).

So if I sum all white pixels on 1st row (top) it should be (0,0)+(1,0)+...+(79,0)=(n(n+1)/2,0), where n=79, right? But the total pixels is N=80. So the centroid of the single row (just to exemplify; the aim is to compute centroid of white area) would be (3160/80,0)?

Thanks.

[tmelorc]

Now it is clear for horizontal regions. I checked by hand with the images

Code: Select all

convert -size 100x200 xc:black -fill white  -draw "rectangle 0,0 79,2"  foo.png
convert -size 100x200 xc:black -fill white  -draw "rectangle 0,0 79,0"    foo.png

and I got the same result as from IM.

Now I have to check for L-shaped image.

Could you confirm if the total pixel number is the number of white pixels or should be the number of pixels in the minimal rectangular region containing the white area?

I believe that some different approach is used by OpenCV.

Thanks.

[snibgo]

The centroid is at the coordinate that is at the arithmetic mean of all the coordinates of the area's pixels. It is the area that matters, not the minimal containing rectangle.

[fmw42]

I used awk to do the computations:

Code: Select all

convert pNcFvOf.png txt: | tail +2 | grep "gray(255)" | tr -cs "0-9\n" " " |\
awk ' { tot = NR; xsum += $1; ysum += $2; } END { print xsum/tot, ysum/tot } '

33.5 34.5

Basically, I am converting the image to txt format and finding the x and coordinates of only the white ( i.e. gray(255) ) pixels (since you only have one regions of white).

see http://www.imagemagick.org/Usage/files/#txt

So IM is doing it correctly in -connected-components

[tmelorc]

I used awk to do the computations:

Code: Select all

convert pNcFvOf.png txt: | tail +2 | grep "gray(255)" | tr -cs "0-9\n" " " |\
awk ' { tot = NR; xsum += $1; ysum += $2; } END { print xsum/tot, ysum/tot } '

Thanks for this suggestion. It is nice for small images. But in my case, I have HD images and this process is too slow comparing with OpenCV.

For example, with an 1700x2340 image, I got the running times:

OpenCV

Code: Select all

real	0m0.101s
user	0m0.086s
sys	0m0.019s

IM convert

Code: Select all

real	0m13.710s
user	0m19.115s
sys	0m0.935s

But now I know how the process works in IM.

Thanks to everybody.

[fmw42]

My AWK result was simply to confirm that ImageMagick was producing the correct result. You should use ImageMagick -connected-components for proper processing.

[tmelorc]

Yes, I agree. The execution time with IM on my HD image was

Code: Select all

real	0m0.764s
user	0m0.766s
sys	0m0.020s

But I think that I discover what is the problem with my OpenCV example. It is extracting a contour from the image to compute its centroid, not the whole component.