19
\$\begingroup\$

I am trying create an algorithm for finding the zero crossing (check that the signs of all the entries around the entry of interest are not the same) in a two dimensional matrix, as part of implementing the Laplacian of Gaussian edge detection filter for a class, but I feel like I'm fighting against Numpy instead of working with it.

import numpy as np

range_inc = lambda start, end: range(start, end+1)

# Find the zero crossing in the l_o_g image
# Done in the most naive way possible
def z_c_test(l_o_g_image):
    print(l_o_g_image)
    z_c_image = np.zeros(l_o_g_image.shape)
    for i in range(1, l_o_g_image.shape[0] - 1):
        for j in range(1, l_o_g_image.shape[1] - 1):
            neg_count = 0
            pos_count = 0
            for a in range_inc(-1, 1):
                for b in range_inc(-1, 1):
                    if a != 0 and b != 0:
                        print("a ", a, " b ", b)
                        if l_o_g_image[i + a, j + b] < 0:
                            neg_count += 1
                            print("neg")
                        elif l_o_g_image[i + a, j + b] > 0:
                            pos_count += 1
                            print("pos")
                        else:
                            print("zero")

            # If all the signs around the pixel are the same
            # and they're not all zero
            # then it's not a zero crossing and an edge. 
            # Otherwise, copy it to the edge map.
            z_c = ((neg_count > 0) and (pos_count > 0))

            if z_c:
                print("True for", i, ",", j)
                print("pos ", pos_count, " neg ", neg_count)
                z_c_image[i, j] = 1

    return z_c_image

Here is the test cases it should pass:

test1 = np.array([[0,0,1], [0,0,0], [0,0,0]])
test2 = np.array([[0,0,1], [0,0,0], [0,0,-1]])
test3 = np.array([[0,0,0], [0,0,-1], [0,0,0]])
test4 = np.array([[0,0,0], [0,0,0], [0,0,0]])
true_result = np.array([[0,0,0], [0,1,0], [0,0,0]])
false_result = np.array([[0,0,0], [0,0,0], [0,0,0]])

real_result1 = z_c_test(test1)
real_result2 = z_c_test(test2)
real_result3 = z_c_test(test3)
real_result4 = z_c_test(test4)

assert(np.array_equal(real_result1, false_result))
assert(np.array_equal(real_result2, true_result))
assert(np.array_equal(real_result3, false_result))
assert(np.array_equal(real_result4, false_result))

How do I vectorize checking a property in a matrix range? Is there a quick way of accessing all of the entries adjacent to an entry in a matrix?

\$\endgroup\$
  • \$\begingroup\$ adjacent meaning N,S,W,E or the 8 (or just 3) around the checked? currently it looks like the NSWE solution, but just to make sure. \$\endgroup\$ – Vogel612 Mar 27 '14 at 8:18
  • \$\begingroup\$ It's supposed to be the 8. \$\endgroup\$ – Seanny123 Mar 27 '14 at 8:26
  • \$\begingroup\$ @Vogel612 As shown in the unit tests and with my very awkward iteration using a and b. \$\endgroup\$ – Seanny123 Mar 27 '14 at 8:36
  • \$\begingroup\$ you might want to have a look at this answer \$\endgroup\$ – Vogel612 Mar 27 '14 at 9:01
  • 2
    \$\begingroup\$ You can try to either express this operation as a convolution, which I am not sure if your check can be expressed as. Otherwise, the function scipy.ndimage.filters.generic_filter with size set to 3 should leave you with only writing a short function doing the check on the vector of neighborhood elements. \$\endgroup\$ – ojdo Apr 17 '14 at 15:12
6
\$\begingroup\$

Here's concise method to get the coordinates of the zero-crossings that seems to work according to my tests :

def zcr(x, y):
    return x[numpy.diff(numpy.sign(y)) != 0]

Some simple test case :

>>> zcr(numpy.array([0, 1, 2, 3, 4, 5, 6, 7]), [1, 2, 3, -1, -2, 3, 4, -4])
array([2, 4, 6])

This is 2d only, but I believe it is easy to adapt to more dimensions.

\$\endgroup\$
1
\$\begingroup\$

One way to get the neighbor coordinates without checking for (a != 0) or (b != 0) on every iteration would be to use a generator. Something like this:

def nborz():
    l = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1),(1,0),(1,1)]
    try:
        while True:
           yield l.pop(0)
    except StopIteration:
        return None
....

for i in range(1,l_o_g_image.shape[0]-1):
    for j in range(1,l_o_g_image.shape[1]-1):
        neg_count = 0
        pos_count = 0
        nbrgen = nborz()
        for (a,b) in nbrgen:
            print "a " + str(a) + " b " + str(b)
            if(l_o_g_image[i+a,j+b] < 0):
                neg_count += 1
                print "neg"
            elif(l_o_g_image[i+a,j+b] > 0):
                pos_count += 1
                print "pos"
            else:
                print "zero"
\$\endgroup\$
  • \$\begingroup\$ Would that actually be faster? \$\endgroup\$ – Seanny123 Apr 20 '14 at 6:02
  • \$\begingroup\$ I would think it might, 1) because it avoids a comparison on every iteration of the inner loops, and 2) because it avoids computation of the index values for the inner loops (counting -1, 0, 1 twice in a nested fashion). However, I have not actually tried it so I don't know for sure. \$\endgroup\$ – Tom Barron Apr 20 '14 at 10:43

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.