ncut and normalized cuts breaking with color and gray images.

[miketoastmacneil]

Description

Looks like ncut and normalized cuts are breaking down. Callback and code given below.
Operating system is mac osx sierra 10.12.6, python version is 3.6.2, scikit-image version is 0.14dev. Relevant image is data.astro(). Code and traceback below.

Have also constructed the graph using RAG separately and tried to access labels, as is done in _label_all, and am given an empty dictionary. Couldn't get very far trying to understand the RAG constructor.

from skimage import io, data
from skimage.color import rgb2gray
from skimage.segmentation import slic, mark_boundaries
from skimage.future.graph import RAG, ncut, cut_normalized

import numpy as np
import matplotlib.pyplot as plt

## Initially tested on gray, breaks in both cases.
astro = data.astronaut()
astro_gray = rgb2gray(astro)
slic_gray = slic(astro_gray, n_segments=200,compactness = 0.1)
slic_color = slic(astro, n_segments=200)
adj_graph_color = RAG(slic_color)
cut_segmentation_color = cut_normalized(slic_color, adj_graph_color)

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-6-180d7478a196> in <module>()
      1 adj_graph_color = RAG(slic_color)
----> 2 cut_segmentation_color = cut_normalized(slic_color,adj_graph_color)

~/Documents/GitHub/scikit-image/skimage/future/graph/graph_cut.py in cut_normalized(labels, rag, thresh, num_cuts, in_place, max_edge)
    129         rag.add_edge(node, node, weight=max_edge)
    130 
--> 131     _ncut_relabel(rag, thresh, num_cuts)
    132 
    133     map_array = np.zeros(labels.max() + 1, dtype=labels.dtype)

~/Documents/GitHub/scikit-image/skimage/future/graph/graph_cut.py in _ncut_relabel(rag, thresh, num_cuts)
    292     # Assign `ncut label` by picking any label from the existing nodes, since
    293     # `labels` are unique, `new_label` is also unique.
--> 294     _label_all(rag, 'ncut label')

~/Documents/GitHub/scikit-image/skimage/future/graph/graph_cut.py in _label_all(rag, attr_name)
    231     """
    232     node = min(rag.nodes())
--> 233     new_label = rag.node[node]['labels'][0]
    234     for n, d in rag.nodes(data=True):
    235         d[attr_name] = new_label

KeyError: 'labels'

[soupault]

@miketoastmacneil have you seen this example - http://scikit-image.org/docs/dev/auto_examples/segmentation/plot_ncut.html?

[jni]

@soupault Ah, I spot the difference now. Nevertheless, this error is super-unhelpful. We should try to catch what is happening and produce a more meaningful error message, something along the lines of "Error: bare RAG was used, without any definition of segment affinities". I guess that might only be helpful to people who know about RAGs. But that's more than you can say for the current error!

[miketoastmacneil]

Thanks for chiming in here. @soupault I have seen that example, the RAG construction is somehow different from what I'm attempting. It should work for grayscale (those are the type of images used in the original paper). @jni As far as I could tell it's an issue with the graph construction, where skimage is relying on another Graph package (Networkx). Can look into the origins myself to get to the bottom of it if that helps.

[jni]

There's two problems here. Only the first one is shown in the error message but the second problem will manifest as soon as we fix the first.

1. We assume the existence of RAG.node[node_idx]['labels'], containing a list of labels pertaining to that node. We do this basically throughout the code, even in RAG.merge_nodes, without requiring that it be added at construction time. This is a major issue and should probably change. My preference is to somehow remove the assumption, because in many applications, it's not really warranted to maintain these lists: the node is the label. However this may not be possible, in which case we should add the lists to the constructor.

2. Even if we fix that, the next part of the ncut code will look for a weight attribute on each edge. When a weight attribute is not found, the RAG should produce a meaningful error message. Not really sure how to make this one happen.

[rfezzani]

I still can reproduce using v0.19 😖