Hierarchical Merging of Region Adjacency Graphs

Region Adjacency Graphs model regions in an image as nodes of a graph with edges between adjacent regions. Superpixel methods tend to over segment images, ie, divide into more regions than necessary. Performing a Normalized Cut and Thresholding Edge Weights are two ways of extracting a better segmentation out of this. What if we could combine two small regions into a bigger one ? If we keep combining small similar regions into bigger ones, we will end up with bigger regions which are significantly different from its adjacent ones. Hierarchical Merging explores this possibility. The current working code can be found at this Pull Request

Code Example

The merge_hierarchical function performs hierarchical merging on a RAG. It picks up the smallest weighing edge and combines the regions connected by it. The new region is adjacent to all previous neighbors of the two combined regions. The weights are updated accordingly. It continues doing so till the minimum edge weight in the graph in more than the supplied thresh value. The function takes a RAG as input where smaller edge weight imply similar regions. Therefore, we use the rag_mean_color function with the default "distance" mode for RAG construction. Here is a minimal code snippet.

from skimage import graph, data, io, segmentation, color


img = data.coffee()
labels = segmentation.slic(img, compactness=30, n_segments=400)
g = graph.rag_mean_color(img, labels)
labels2 = graph.merge_hierarchical(labels, g, 40)
g2 = graph.rag_mean_color(img, labels2)

out = color.label2rgb(labels2, img, kind='avg')
out = segmentation.mark_boundaries(out, labels2, (0, 0, 0))
io.imsave('out.png',out)

I arrived at the threshold 40 after some trial and error. Here is the output.

out

The drawback here is that the thresh argument can vary significantly depending on image to image.

Comparison with Normalized Cut

Loosely speaking the normalized cut follows a top-down approach where as the hierarchical merging follow a bottom-up approach. Normalized Cut starts with the graph as a whole and breaks it down into smaller parts. On the other hand hierarchical merging, starts with individual regions and merges them into bigger ones till a criteria is reached. The Normalized Cut however, is much more robust and requires little tuning of its parameters as images change. Hierarchical merging is a lot faster, even though most of its computation logic is written in Python.

Effect of change in threshold

Setting a very low threshold, will not merge any regions and will give us back the original image. A very large threshold on the other hand would merge all regions and give return the image as just one big blob. The effect is illustrated below.

threshold=10

10

threshold=20

20

threshold=40

40

threshold=70

70

threshold=100

70

Hierarchical Merging in Action

With this modification the following code can output the effect of all the intermediate segmentation during each iteration.

from skimage import graph, data, io, segmentation, color
import time
from matplotlib import pyplot as plt


img = data.coffee()
labels = segmentation.slic(img, compactness=30, n_segments=400)
g = graph.rag_mean_color(img, labels)
labels2 = graph.merge_hierarchical(labels, g, 60)

c = 0

out = color.label2rgb(graph.graph_merge.seg_list[-10], img, kind='avg')
for label in graph.graph_merge.seg_list:
    out = color.label2rgb(label, img, kind='avg')
    out = segmentation.mark_boundaries(out, label, (0, 0, 0))
    io.imsave('/home/vighnesh/Desktop/agg/' + str(c) + '.png', out)
    c += 1

I then used avconv -f image2 -r 3 -i %d.png -r 20 car.mp4 to output a video. Below are a few examples.

In each of these videos, at every frame, a boundary dissapears. This means that the two regions separated by that boundary are merged. The frame rate is 5 FPS, so more than one region might be merged at a time.

Coffee Image

coffee

Car Image

car

Baseball Image

baseball

Advertisements

31 thoughts on “Hierarchical Merging of Region Adjacency Graphs

  1. Pingback: GSoC 2014 – Signing off | A Simple Progammer's Blog
  2. Hi Vighnesh,
    I try to run this code using Anaconda with python 2.7 on win8.
    This comes with skimage preinstalled, but some methods doesnt recognice by it, like regionprops(), graph.rag_mean_color()…it prompts an error message like this: ‘module’ object has no attibute ‘rag_mean_color’
    why this is happening? maybe i have another version?
    Any advice?
    thanks in advance, Jaime

    • Hello

      The hierarchical merging code hasn’t been merged, and `rag_mean_color` isn’t there in the latest release.
      For the codhttps://vcansimplify.wordpress.com/2014/08/17/hierarchical-merging-of-region-adjacency-graphs/?replytocom=254#responde in this post, you need to pull from here
      https://github.com/scikit-image/scikit-image/pull/1100

      For the other things, pulling from the master branch is sufficient.

      Let me know if you are still facing issues.

      Thanks
      Vighnesh

      • Hi Vighnesh,

        Sorry if I didnt understand your point correctly.
        You mean, that I have to copy the code from master branch and replace inside Anaconda/Lib/site-packages/skimage/?
        I upgraded the package before to run again, but it shows me the same error message.
        Thanks for your soon asnwer,

        Jaime

      • Hi
        First you need to install git.

        Run

        sudo apt-get install git

        Then clone the master branch and install latest code.

        git clone https://github.com/scikit-image/scikit-image.git
        cd scikit-image
        sudo python setup.py develop

        This should get the functions like rag_mean_color etc running. At any point of time, to get the changes from the master branch do.


        git checkout master
        git fetch origin
        git merge origin/master
        sudo python setup.py develop

        To merge my pull request.

        git branch test-branch
        git checkout test-branch
        git pull https://github.com/vighneshbirodka/scikit-image.git ha
        sudo python setup.py develop

        I haven’t testes these commands, so let me know if there is an issue. I also suggest that you get some familiarity with git. A good place to start is here.

        https://try.github.io/levels/1/challenges/1

  3. Hi Vighnesh,

    Does this instrucctions works the same way under Win8 ?
    I have installed git for windows, and I have Anaconda running under win8, 64-bit, python 2.7

    Thanks in advance, Jaime

  4. Hi Vighnesh,

    I followed your instructions, but I got some error and warnings like these:
    fatal: unable to checkout working tree
    warning: Clone succeeded, but checkout failed

    Jaime

  5. Hi Vignesh

    I have two skimage versions installed on my computer:

    1) skimage pre-build Anaconda (latest):
    C:/Anaconda/Lib/site-packages/skimage/graph/ #no rag.py

    2) skimage cloned from your github (latest):
    C:/Users/Jaime/scikit-image/graph/rag.py

    I couldnt to run your latest code (pulled from github), because it throws an error about rag.py file, althougth it is already installed. Maybe, I need to modify my pythonpath? or something like that?
    I am running it by console and spyder IDE too, but it doesnt work either.

    I apologize with you, if this is a easy topic, but I am not an expert about this. Any advice would be very appreciated.

    thanks in advance, Jaime

      • Hi Vighnesh,

        When I try to run your code of Hierarchical merging (this page) using my clone version from your github code (not Anaconda preinstalled), I open python console from this location, I mean, C:/Users/Jaime/Scikit-image/skimage
        Then, I start to run the code interactively:

        >>>from skimage import graph,data,io,segmentation,color
        ImportError: cannot import name BytesIO

        Previously, before I reinstalled everything (Anaconda and skimage), I got this error too, but when I resolved it, appears other error like IntEnum, and so on…I dont know why these errors appear, because I have latest version, and I suppose these dependencies shouldnt affect.

        Thank very much, Jaime

    • Hi Vighnesh,

      Yeah, I ran it again and i saw something wrong after the instrucction:
      >>> python setup.py develop
      running…
      building…
      writing…
      warning: no files found matching ‘setup.cfg’
      no previously-included directories found matchin ‘doc\build’
      ….
      customiza Mingw32CCompiler
      building ‘skimage.restoration._unwrap_2d’ extension
      compiling C sources
      C compiler: gcc -O2 -Wall -Wstrict-prototypes
      compile options…

      error: Command “g++ -shared build\temp.win32-2.7\Release\skimage\restoration\_unwrap-2d.o build\temp.win32-2.7\Release\skimage\restoration\unwrap_2d_ljmu.o -LC:\Anaconda\libs -LC:\Anaconda\PCbuild -lpython27 -lmsvcr90 -o skimage\restoration\_unwrap_2d.pyd” failed with exit status 1

      So, maybe this setup.py is for linux version? I am on windows.

      Jaime

  6. Hi Vighnesh,

    I followed the MinGW install instruction, it works ok
    I ran the setup.py file again, and it shows the same error message…
    I hope you can give some advices about your windows try,

    thanks, Jaime

      • Hi Vighnesh,

        I send the console screen after commands by email (vighneshbirodkar@gmail.com), because it is too long.

        Jaime

      • Hi Vighnesh,

        I learn how to copy from console, this is the result:

        C:\>echo %path%
        C:\Program Files (x86)\Intel\iCLS Client\;C:\Program Files\Intel\iCLS Client\;C:
        \WINDOWS\system32;C:\WINDOWS;C:\WINDOWS\System32\Wbem;C:\WINDOWS\System32\Window
        sPowerShell\v1.0\;C:\Program Files (x86)\EgisTec MyWinLocker\x64;C:\Program File
        s (x86)\EgisTec MyWinLocker\;C:\Program Files (x86)\Intel\OpenCL SDK\2.0\bin\x86
        ;C:\Program Files (x86)\Intel\OpenCL SDK\2.0\bin\x64;C:\Program Files\Intel\Inte
        l(R) Management Engine Components\DAL;C:\Program Files\Intel\Intel(R) Management
        Engine Components\IPT;C:\Program Files (x86)\Intel\Intel(R) Management Engine C
        omponents\DAL;C:\Program Files (x86)\Intel\Intel(R) Management Engine Components
        \IPT;C:\Program Files (x86)\Java\jdk1.7.0_13\bin\;C:\Program Files (x86)\Java\jd
        k1.7.0_13\jre\bin\client;C:\WINDOWS;C:\WINDOWS\System32;C:\Program Files (x86)\J
        ava\jdk1.7.0_13\bin; C:\Python33\python.exe;C:\Anaconda\Lib\site-packages\graphv
        iz\; C:\Program Files\R\R-2.15.2\bin\x64\R\;C:\Anaconda;C:\Anaconda\Scripts;C:\M
        inGW\bin;

        C:\>g++ –version
        g++.exe (GCC) 4.7.0 20111219 (experimental)
        Copyright (C) 2011 Free Software Foundation, Inc.
        This is free software; see the source for copying conditions. There is NO
        warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

        Jaime

  7. distutils.cfg file:
    ——————–
    [build]
    compiler = mingw32

    python setup.py develop:
    ————————————

    C:\Users\Jaime\scikit-image>python setup.py develop
    running develop
    running build_scripts
    running egg_info
    running build_src
    build_src
    building extension “skimage._shared.geometry” sources
    building extension “skimage._shared.transform” sources
    building extension “skimage.draw._draw” sources
    building extension “skimage.feature.corner_cy” sources
    building extension “skimage.feature.censure_cy” sources
    building extension “skimage.feature.orb_cy” sources
    building extension “skimage.feature.brief_cy” sources
    building extension “skimage.feature._texture” sources
    building extension “skimage.feature._hessian_det_appx” sources
    building extension “skimage.restoration._unwrap_1d” sources
    building extension “skimage.restoration._unwrap_2d” sources
    building extension “skimage.restoration._unwrap_3d” sources
    building extension “skimage.restoration._denoise_cy” sources
    building extension “skimage.filter._ctmf” sources
    building extension “skimage.filter.rank.core_cy” sources
    building extension “skimage.filter.rank.generic_cy” sources
    building extension “skimage.filter.rank.percentile_cy” sources
    building extension “skimage.filter.rank.bilateral_cy” sources
    building extension “skimage.graph._spath” sources
    building extension “skimage.graph._mcp” sources
    building extension “skimage.graph.heap” sources
    building extension “skimage.graph._ncut_cy” sources
    building extension “skimage.io._plugins._colormixer” sources
    building extension “skimage.io._plugins._histograms” sources
    building extension “skimage.measure._ccomp” sources
    building extension “skimage.measure._find_contours_cy” sources
    building extension “skimage.measure._moments” sources
    building extension “skimage.measure._marching_cubes_cy” sources
    building extension “skimage.morphology.cmorph” sources
    building extension “skimage.morphology._watershed” sources
    building extension “skimage.morphology._skeletonize_cy” sources
    building extension “skimage.morphology._pnpoly” sources
    building extension “skimage.morphology._convex_hull” sources
    building extension “skimage.morphology._greyreconstruct” sources
    building extension “skimage.transform._hough_transform” sources
    building extension “skimage.transform._warps_cy” sources
    building extension “skimage.transform._radon_transform” sources
    building extension “skimage.segmentation._felzenszwalb_cy” sources
    building extension “skimage.segmentation._quickshift” sources
    building extension “skimage.segmentation._slic” sources
    building data_files sources
    build_src: building npy-pkg config files
    writing requirements to scikit_image.egg-info\requires.txt
    writing scikit_image.egg-info\PKG-INFO
    writing top-level names to scikit_image.egg-info\top_level.txt
    writing dependency_links to scikit_image.egg-info\dependency_links.txt
    writing entry points to scikit_image.egg-info\entry_points.txt
    reading manifest file ‘scikit_image.egg-info\SOURCES.txt’
    reading manifest template ‘MANIFEST.in’
    warning: no files found matching ‘setup.cfg’
    no previously-included directories found matching ‘doc\build’
    no previously-included directories found matching ‘doc\gh-pages’
    writing manifest file ‘scikit_image.egg-info\SOURCES.txt’
    running build_ext
    customize Mingw32CCompiler
    customize Mingw32CCompiler using build_ext
    building ‘skimage.restoration._unwrap_2d’ extension
    compiling C sources
    C compiler: gcc -O2 -Wall -Wstrict-prototypes

    compile options: ‘-D__MSVCRT_VERSION__=0x0900 -IC:\Anaconda\lib\site-packages\nu
    mpy\core\include -IC:\Anaconda\lib\site-packages\numpy\core\include -IC:\Anacond
    a\include -IC:\Anaconda\PC -c’
    gcc -O2 -Wall -Wstrict-prototypes -D__MSVCRT_VERSION__=0x0900 -IC:\Anaconda\lib\
    site-packages\numpy\core\include -IC:\Anaconda\lib\site-packages\numpy\core\incl
    ude -IC:\Anaconda\include -IC:\Anaconda\PC -c skimage\restoration\unwrap_2d_ljmu
    .c -o build\temp.win32-2.7\Release\skimage\restoration\unwrap_2d_ljmu.o
    Found executable C:\Anaconda\Scripts\gcc.bat
    gcc -O2 -Wall -Wstrict-prototypes -D__MSVCRT_VERSION__=0x0900 -IC:\Anaconda\lib\
    site-packages\numpy\core\include -IC:\Anaconda\lib\site-packages\numpy\core\incl
    ude -IC:\Anaconda\include -IC:\Anaconda\PC -c skimage\restoration\_unwrap_2d.c –
    o build\temp.win32-2.7\Release\skimage\restoration\_unwrap_2d.o
    g++ -shared build\temp.win32-2.7\Release\skimage\restoration\_unwrap_2d.o build\
    temp.win32-2.7\Release\skimage\restoration\unwrap_2d_ljmu.o -LC:\Anaconda\libs –
    LC:\Anaconda\PCbuild -lpython27 -lmsvcr90 -o skimage\restoration\_unwrap_2d.pyd
    Found executable C:\Anaconda\Scripts\g++.bat
    build\temp.win32-2.7\Release\skimage\restoration\_unwrap_2d.o:_unwrap_2d.c:(.tex
    t+0x4eab): undefined reference to `__imp__unwrap2D’
    collect2.exe: error: ld returned 1 exit status
    error: Command “g++ -shared build\temp.win32-2.7\Release\skimage\restoration\_un
    wrap_2d.o build\temp.win32-2.7\Release\skimage\restoration\unwrap_2d_ljmu.o -LC:
    \Anaconda\libs -LC:\Anaconda\PCbuild -lpython27 -lmsvcr90 -o skimage\restoration
    \_unwrap_2d.pyd” failed with exit status 1

  8. Hello Vighnesh
    I installed ubuntu 14, git, and clone scikit-image too
    When I execute your instructions it generates this error:
    jaimebayes@OptiPlex:~$ cd scikit-image
    jaimebayes@OptiPlex:~/scikit-image$ git checkout master
    skimage/graph/rag.py: needs merge
    error: you need to resolve your current index first
    jaimebayes@OptiPlex:~/scikit-image$ git fetch origin
    jaimebayes@OptiPlex:~/scikit-image$ git merge origin/master
    error: ‘merge’ is not possible because you have unmerged files.
    hint: Fix them up in the work tree,
    hint: and then use ‘git add/rm ‘ as
    hint: appropriate to mark resolution and make a commit,
    hint: or use ‘git commit -a’.
    fatal: Exiting because of an unresolved conflict.
    jaimebayes@OptiPlex:~/scikit-image$

    can you help me to resolve this?
    thanks in advance, Jaime

  9. Hi Vighnesh,
    I try to run this code but I got this error:merge_hierarchical() takes exactly 7 arguments(3 given).
    I dont know how to use the merge_hierarchical(), Can you tell me?
    Thank you very much.

  10. Hi Vighnesh,

    I found that your code is very useful, so I want to know more about the principles of your code.
    Are there any references relate to it?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s