1
$\begingroup$

I have following picture

enter image description here

which I extract the contour from. The contour looks like following

enter image description here

I am wondering, for any pixel in the image, how do I determine if it is inside the contour or not? Say "inside" here means any pixel in the body.

If possible, I'd prefer simple, direct, and elegant algorithm. Thanks.

$\endgroup$
  • $\begingroup$ @StanleyPawlukiewicz Hi Stanley, care to point it out a little more? Thanks. $\endgroup$ – Nick X Tsui Sep 2 '18 at 14:17
1
$\begingroup$

I am not in the image processing field, but here is an approach from my control loop background that I believe would apply as an elegant solution for determining if a pixel is inside a contour. This would be to treat the image as a complex plane and then use the Cauchy Argument Principle (from 1831!!!) to determine if the pixel is inside or outside the contour.

The details and background are below, but as an algorithm you would do the following:

Treat your pixel of interest and your contour as a complex number, meaning a pixel at an x, y location is represented as x+ jy (I am an engineer so trained to you j instead of i). Using complex number subtraction, subtract the pixel from every point on your contour (which is a new vector with magnitude and phase) and measure the phase of this new vector. Continue along the contour while keeping track of the minimum and maximum phase value in the results after the subtraction. Once the contour is complete (you have completely enclosed your pixel) determine the maximum - minimum phase. If it is 2$pi$ the pixel is inside your contour, if not then it is outside.

See figure below for an introduction to the Cauchy Argument prinicple, and then I will try to explain how this becomes the algorithmic solution above. From this you may define other similar algorithms depending on the details of your contour, such as you will notice that the phase in the example given where the contour phase keeps increasing will also keep increasing when the pixel is inside the coutour, but will increase and then decrease when it is outside.

Cauchy Argument Principle

To explain the principle I will need to explain (in simplest terms) the idea of poles and zeros and encirclement on the complex plane. For your case we could simply identify the one pixel as a "zero" and proceed from there, which makes the explanation even simpler, so I will avoid any details on encircling poles. (My plot is titled "Nyquist Plot Background" as this is the theory behind the Nyquist Plot that is used in classical control theory).

Given a ratio of polynomials, the poles are the values from a complex plane that would result in the ratio being infinity, and the zeros are the values that would result in the ratio being zero. Typically the polynomials are factors into first order functions to readily reveal the pole and zero locations. For example:

$$H(s) = \frac{(s+2)}{(s+3)(s+5)}$$ would have a zero at s= -2 and two poles at s=-3 and s=-5. These are the values that would make the ratio go to zero and infinity. At this point for a test of a single pixel, we can proceed with the idea of a single zero so will use that going forward.

In terms of an image with two axis x and y, x would correspond to the real numbers in this case, and y would correspond to imaginary numbers (the solution in the end will be very simple and elegant, but we need to use complex numbers to use it). So in the case above, the zero would be on the image at x= -2 and y = 0. To position a zero at an arbitrary location with x and y values we would use $(s - (x+jy))$ as the zero.

That said, observe how the Cauchy Argument Principle and complex mapping works in the case of a single zero:

In the following figure, we have a mapping of a zero at location x= -2, y=0 defined by the function $$H(s) = s+2$$

The mapping of H(s) for the example contour shown is on the right. What the mapping is specifically is to take each point on the contour and subtract it from the zero. So for each point $(x_n, y_n)$ on the contour, and the pole at $(x_z, y_z)$ we would get the result $(x_n+j y_n) - (x_z+j y_z)$ which is a complex vector with the magnitude and phase just as shown by the blue vector on the left in the plot below. Note that the magnitude is simply the geometric length between these two points in 2D space, and the angle is the angle found by moving the zero to the origin; by subtracting the two, we are simply moving the zero to the origin which is the complete mapping in the case of the zero (simple!). The Cauchy Principle reduces to saying if you encircle the zero that is inside the contour, the mapping will encircle the origin in the same direction.

mapping of zero inside contour

In contrast, if the zero is outside the contour, as in the plot below with the zero at x= -4, y =0, the mapping will not enclose the origin.

mapping of zero outside contour

So using this, we can position your one pixel to be the zero as a complex number at the x,y position, and complete the mapping by subtracting each x,y position on your contour to each x,y position on your pixel. Now to algorithmically test that the result encircles the origin, note the phase for each of the two cases above. For the case of encirclement, the phase will go from 0 to $2\pi$ always. For the case when we don't encircle the origin the phase can never extend completely from 0 to $2\pi$.

$\endgroup$
0
$\begingroup$

Finding algorithms related to standard (infinite continuous) geometry onto a finite discretized pixel grid belongs to a class of well-studied questions, and the keyword "discrete geometry" can be a pointer. For instance, drawing a line in the plane is easy, doing that efficiently on a pixel grid led for instance to the famous Bresenham line drawing algorithm. Such topics are covered e.g. in Chen, Li M., 2014, Digital and Discrete Geometry. Theory and Algorithms (pdf).

Some assumptions could be useful to narrow the number of solutions down. Without more precise properties for the contour (convexity, etc.) I will assume that the contour is a simple closed curve "inside" the image (it does not touch the borders of the picture), and is not crossed. Then, you can treat its discretization as a regular polygon (without crossing edges) and look for algorithms checking whether a point is inside a polygon.

You can then invest in ray casting algorithms, as described for instance in How can I determine whether a 2D Point is within a Polygon? with a piece of a solution:

The easiest algorithm, that can handle all three cases above and is still pretty fast is named ray casting. The idea of the algorithm is pretty simple: Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon.

$\endgroup$
0
$\begingroup$

You could do a flood fill from one corner (or more, if needed) using a colour that is different from the contour or background. Then you just need to check the colour of the pixel you want to know about. You can tell check instantly whether any pixel is inside, outside or on the contour.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.