Parallel edge detection

canny edge detection
types of edge detection
best edge detection algorithm
edge detection output
why canny edge detection is better
edge detection python
canny edge detection tutorial
fastest edge detection algorithm

I am working on a problem (from Algorithms by Sedgewick, section 4.1, problem 32) to help my understanding, and I have no idea how to proceed.

"Parallel edge detection. Devise a linear-time algorithm to count the parallel edges in a (multi-)graph. Hint: maintain a boolean array of the neighbors of a vertex, and reuse this array by only reinitializing the entries as needed."

Where two edges are considered to be parallel if they connect the same pair of vertices

Any ideas what to do?

I think we can use BFS for this .

Main idea is to be able to tell if to tell if two or more paths exist between two nodes or not , so for this we can use a set and see if adjacent nodes corresponding to a Node's adjacent list already is in the set.

This uses O(n) extra space but has O(n) time complexity. boolean bfs(int start){

 Queue<Integer> q = new Queue<Integer>();       // get a Queue
 boolean[] mark = new boolean[num_of_vertices]; 
 mark[start] = true;                            // put 1st node into Queue
 q.add(start); 
 while(!q.isEmpty()){
    int current = q.remove();
    HashSet<Integer> set = new HashSet<Integer>(); /* use a hashset for 
                                    storing nodes of current adj. list*/ 
    ArrayList<Integer> adjacentlist= graph.get(current);   // get adj. list 
    for(int x : adjacentlist){
        if(set.contains(x){  // if it already had a edge current-->x
          return true;       // then we have our parallel edge
        }
        else set.add(x);     // if not then we have a new edge 

        if(!marked[x]){      // normal bfs routine
            mark[x]=true;
            q.add(x);
        }
    }
 }
}// assumed graph has ArrayList<ArrayList<Integer>> representation    
 // undirected 

Assignment 2: Parallel Edge Detection (Due Date: Thursday October , I think we can use BFS for this. Main idea is to be able to tell if two or more paths exist between two nodes or not, so for this, we can use a set  "Parallel edge detection. Devise a linear-time algorithm to count the parallel edges in a (multi-)graph. Hint: maintain a boolean array of the neighbors of a vertex, and reuse this array by only reinitializing the entries as needed." Where two edges are considered to be parallel if they connect the same pair of vertices

Assuming that the vertices in your graph are integers 0 .. |V|.

If your graph is directed, edges in the graph are denoted (i, j).

This allows you to produce a unique mapping of any edge to an integer (a hash function) which can be found in O(1).

h(i, j) = i * |V| + j 

You can insert/lookup the tuple (i, j) in a hash table in amortised O(1) time. For |E| edges in the adjacency list, this means the total running time will be O(|E|) or linear in the number of edges in the adjacency list.

A python implementation of this might look something like this:

def identify_parallel_edges(adj_list):
    # O(n) list of edges to counts
    # The Python implementation of tuple hashing implements a more sophisticated
    # version of the approach described above, but is still O(1)
    edges = {}
    for edge in adj_list:
        if edge not in edges:
            edges[edge] = 0
        edges[edge] += 1

    # O(n) filter non-parallel edges
    res = []
    for edge, count in edges.iteritems():
        if count > 1:
            res.append(edge)
    return res

edges = [(1,0),(2,1),(1,0),(3,4)]
print identify_parallel_edges(edges)

Parallel edge detection, Edge detection is one of the most important paradigm of Image processing. Images contain millions of pixel and each pixel information is independent of its. The proposed parallel Otsu-Canny edge detection algorithm performs better than other traditional edge detection algorithms. The parallel approach reduced the running time by approximately 67.2&#x25; on a Hadoop cluster architecture consisting of 5 nodes with a dataset of 60,000 images.

I am also working on this problem, please help me check whether my thinking is right or not.

It seems that the hint told us that we could reuse the code section in Cycle.java. (https://algs4.cs.princeton.edu/41graph/Cycle.java.html)

// does this graph have two parallel edges?
// side effect: initialize cycle to be two parallel edges
private boolean hasParallelEdges(Graph G) {
    marked = new boolean[G.V()];

    for (int v = 0; v < G.V(); v++) {

        // check for parallel edges incident to v
        for (int w : G.adj(v)) {
            if (marked[w]) {
                cycle = new Stack<Integer>();
                cycle.push(v);
                cycle.push(w);
                cycle.push(v);
                return true;
            }
            marked[w] = true;
        }

        // reset so marked[v] = false for all v
        for (int w : G.adj(v)) {
            marked[w] = false;
        }
    }
    return false;
}

As the hint told us, instead of initializing the whole array of G.V() size, we could initialize the entries which were connected by the former vertex. Then did the recursion for every vertexes in the graph via BFS. Thus we would the time consuming should be on the same level with BFS, O(V+E), which is linear.

// these shall be done in the constructor
count = 0;
marked = new boolean[G.V()];

// count the number of parallel edges
private boolean parallelEdges(Graph G, int v) {
    for (int v = 0; v < G.V(); v++) {

        // check for parallel edges incident to v
        for (int w : G.adj(v)) {
            if (marked[w]) {
                count++; // the number of parallel edges
            }
            marked[w] = true;
        }

        // reset so marked[v] = false for all v
        for (int w : G.adj(v)) {
            marked[w] = false;
        }

        for (int w : G.adj(v)) {
            markedForBFS[v] = true;
            for (int w : G.adj(v))
                if (!markedForBFS[v])
                    parallelEdges(G, w);
        }
    }
    return false;
}

I think the key is not mixing two marked arrays together.

Parallel edge detection by SOBEL algorithm using CUDA C, This paper discusses a simple parallel edge detection algorithm which takes the parallel edge as one entity instead of two separate edges. A special edge  Scalable Edge detection on images. Contribute to suvamsh/Parallel-Edge-Detection development by creating an account on GitHub.

Parallel Edge Detection, This operator involves the use of a multi-stage algorithm to detect edges in a wide range of images. Edge detection is at the forefront of image processing and​  Parallel edges often provide a unique local feature for part recognition in manufacturing automation or robotic guidance applications. This paper discusses a simple parallel edge detection algorithm which takes the parallel edge as one entity instead of two separate edges.

[PDF] High Performance Canny Edge Detector using Parallel , In this paper, a novel resolution free parallel implementation algorithm for gradient based edge detection, namely EDENP, is proposed. The key  Scalable Edge detection on images. Contribute to suvamsh/Parallel-Edge-Detection development by creating an account on GitHub.

A Resolution-Free Parallel Algorithm for Image Edge Detection , PDF | Edge detection is a considerably important factor in image or video processing. Detection of edges plays a significant role in image  Parallel edge detection by SOBEL algorithm using CUDA C Abstract: Edge detection is one of the most important paradigm of Image processing. Images contain millions of pixel and each pixel information is independent of its neighbouring pixel.

Comments
  • What have you tried? Don't worry about getting O(n) for now, just try to count the parallel edges. How would you do it?
  • The only thing I can think of is the obvious way of doing it. Assuming I have an adjacency list, I loop through to each element of the list and count the number of repetitions, I also skip the double counts
  • Without more information about your definition of a graph no-one is going to be give you a good answer. A graph is a set of vertices and edges G = (V, E), but there is no notion of anything geometric that goes with that. Is the graph embedded in a lattice? If so what type (square, triangular, other?).
  • The graph is given as an adjacency list. Meaning, this is a 2d array where each (i,J) denotes if the two vertices have an edge between them.
  • also assume the graph is undirected and simple
  • I'm not sure what you mean by (i, j) = (min(i,j), max(i,j)). The graph I am dealing with is undirected
  • Also the data structures I am dealing with are arrays (adjacency lists or matrices)