Fast calculation of v-disparity with OpenCV-Function calcHist
Question: Based on a disparity matrix from a passive stereo-camera system i need to
calculate a v-disparity representation for obstacle detection with OpenCV.

A working implementation is **not** the problem. The problem is to do it
fast...

(One) Reference for v-Disparity: Labayrade, R. and Aubert, D. and Tarel, J.P.
Real time obstacle detection in stereovision on non flat road geometry through
v-disparity representation

The basic in short, to get the v-disparity (figure
[1](http://i.stack.imgur.com/fPvsg.png)), is to analyze the rows of the
disparity-matrix (figure [2](http://i.stack.imgur.com/YXYvf.png)) an represent
the result as a histogram for each row over the disparity values. u-disparity
(figure [3](http://i.stack.imgur.com/R0qSt.png)) is the same on the columns of
the disparity-matrix. (All figures are false-colored.)

I have implement the "same" in Python and C++. The speed in Python is
acceptable but in C++ i get for the u- and v-disparity a time round about a
half second (0.5 s).

_(1. edit: due to the separate time measurement, only the calculation of the
u-histogram takes a big amount of time...)_

This leads me to following questions:

  1. Is it possible to avoid the loops for the line-wise calculation of the histogram? Is there a "trick" to do it with one call of `calcHist`-Function from OpenCV? Perhaps with the dimensions?

  2. Is it in C++ just bad-coded and the runtime-issue are not related to the loops used for calculation?

Thanks, all

* * *

Working implementation in Python:

    
    
    #!/usr/bin/env python2
    #-*- coding: utf-8 -*-
    #
    # THIS SOURCE-CODE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    # IMPLIED. IN NO  EVENT WILL THE AUTHOR BE HELD LIABLE FOR ANY DAMAGES ARISING FROM
    # THE USE OF THIS SOURCE-CODE. USE AT YOUR OWN RISK.
    
    import cv2
    import numpy as np
    import time
    
    def draw_object(image, x, y, width=50, height=100):
        color = image[y, x]
        image[y-height:y, x-width//2:x+width//2] = color
    
    
    IMAGE_HEIGHT = 600
    IMAGE_WIDTH = 800
    
    while True:
    
        max_disp = 200
    
        # create fake disparity
        image = np.zeros((IMAGE_HEIGHT, IMAGE_WIDTH), np.uint8)
    
        for c in range(IMAGE_HEIGHT)[::-1]:
            image[c, ...] = int(float(c) / IMAGE_HEIGHT * max_disp)
    
        draw_object(image, 275, 175)
        draw_object(image, 300, 200)
        draw_object(image, 100, 350)
    
        # calculate v-disparity
        vhist_vis = np.zeros((IMAGE_HEIGHT, max_disp), np.float)
        for i in range(IMAGE_HEIGHT):
            vhist_vis[i, ...] = cv2.calcHist(images=[image[i, ...]], channels=[0], mask=None, histSize=[max_disp],
                                             ranges=[0, max_disp]).flatten() / float(IMAGE_HEIGHT)
    
    
        vhist_vis = np.array(vhist_vis * 255, np.uint8)
        vblack_mask = vhist_vis < 5
        vhist_vis = cv2.applyColorMap(vhist_vis, cv2.COLORMAP_JET)
        vhist_vis[vblack_mask] = 0
    
        # calculate u-disparity
        uhist_vis = np.zeros((max_disp, IMAGE_WIDTH), np.float)
        for i in range(IMAGE_WIDTH):
            uhist_vis[..., i] = cv2.calcHist(images=[image[..., i]], channels=[0], mask=None, histSize=[max_disp],
                                             ranges=[0, max_disp]).flatten() / float(IMAGE_WIDTH)
    
        uhist_vis = np.array(uhist_vis * 255, np.uint8)
        ublack_mask = uhist_vis < 5
        uhist_vis = cv2.applyColorMap(uhist_vis, cv2.COLORMAP_JET)
        uhist_vis[ublack_mask] = 0
    
    
        image = cv2.applyColorMap(image, cv2.COLORMAP_JET)
    
    
        cv2.imshow('image', image)
    
        cv2.imshow('vhist_vis', vhist_vis)
        cv2.imshow('uhist_vis', uhist_vis)
    
        cv2.imwrite('disparity_image.png', image)
        cv2.imwrite('v-disparity.png', vhist_vis)
        cv2.imwrite('u-disparity.png', uhist_vis)
    
    
        if chr(cv2.waitKey(0)&255) == 'q':
            break
    

* * *

Working implementation in C++:

    
    
    #include <iostream>
    #include <stdlib.h>
    
    #include <ctime>
    
    #include <opencv2/opencv.hpp>
    
    
    using namespace std;
    
    void draw_object(cv::Mat image, unsigned int x, unsigned int y, unsigned int width=50, unsigned int height=100)
    {
        image(cv::Range(y-height, y), cv::Range(x-width/2, x+width/2)) = image.at<unsigned char>(y, x);
    }
    
    
    int main()
    {
        unsigned int IMAGE_HEIGHT = 600;
        unsigned int IMAGE_WIDTH = 800;
        unsigned int MAX_DISP = 250;
        unsigned int CYCLE = 0;
    
        //setenv("QT_GRAPHICSSYSTEM", "native", 1);
    
    
        // === PREPERATIONS ==
        cv::Mat image = cv::Mat::zeros(IMAGE_HEIGHT, IMAGE_WIDTH, CV_8U);
        cv::Mat uhist = cv::Mat::zeros(IMAGE_HEIGHT, MAX_DISP, CV_32F);
        cv::Mat vhist = cv::Mat::zeros(MAX_DISP, IMAGE_WIDTH, CV_32F);
    
        cv::Mat tmpImageMat, tmpHistMat;
    
        float value_ranges[] = {(float)0, (float)MAX_DISP};
        const float* hist_ranges[] = {value_ranges};
        int channels[] = {0};
        int histSize[] = {MAX_DISP};
    
    
        struct timespec start, finish;
        double elapsed;
    
        while(1)
        {
            CYCLE++;
    
            // === CLEANUP ==
            image = cv::Mat::zeros(IMAGE_HEIGHT, IMAGE_WIDTH, CV_8U);
            uhist = cv::Mat::zeros(IMAGE_HEIGHT, MAX_DISP, CV_32F);
            vhist = cv::Mat::zeros(MAX_DISP, IMAGE_WIDTH, CV_32F);
    
            // === CREATE FAKE DISPARITY WITH OBJECTS ===
            for(int i = 0; i < IMAGE_HEIGHT; i++)
                image.row(i) = ((float)i / IMAGE_HEIGHT * MAX_DISP);
    
            draw_object(image, 200, 500);
            draw_object(image, 525 + CYCLE%100, 275);
            draw_object(image, 500, 300 + CYCLE%100);
    
            clock_gettime(CLOCK_MONOTONIC, &start);
    
            // === CALCULATE V-HIST ===
            for(int i = 0; i < IMAGE_HEIGHT; i++)
            {
                tmpImageMat = image.row(i);
                vhist.row(i).copyTo(tmpHistMat);
    
                cv::calcHist(&tmpImageMat, 1, channels, cv::Mat(), tmpHistMat, 1, histSize, hist_ranges, true, false);
    
                vhist.row(i) = tmpHistMat.t() / (float) IMAGE_HEIGHT;
            }
    
            clock_gettime(CLOCK_MONOTONIC, &finish);
            elapsed = (finish.tv_sec - start.tv_sec);
            elapsed += (finish.tv_nsec - start.tv_nsec) * 1e-9;
            cout << "V-HIST-TIME: " << elapsed << endl;
    
            clock_gettime(CLOCK_MONOTONIC, &start);
    
            // === CALCULATE U-HIST ===
            for(int i = 0; i < IMAGE_WIDTH; i++)
            {
                tmpImageMat = image.col(i);
                uhist.col(i).copyTo(tmpHistMat);
    
                cv::calcHist(&tmpImageMat, 1, channels, cv::Mat(), tmpHistMat, 1, histSize, hist_ranges, true, false);
    
                uhist.col(i) = tmpHistMat / (float) IMAGE_WIDTH;
            }
    
            clock_gettime(CLOCK_MONOTONIC, &finish);
            elapsed = (finish.tv_sec - start.tv_sec);
            elapsed += (finish.tv_nsec - start.tv_nsec) * 1e-9;
            cout << "U-HIST-TIME: " << elapsed << endl;
    
            // === PREPARE AND SHOW RESULTS ===
    
            uhist.convertTo(uhist, CV_8U, 255);
            cv::applyColorMap(uhist, uhist, cv::COLORMAP_JET);
    
            vhist.convertTo(vhist, CV_8U, 255);
            cv::applyColorMap(vhist, vhist, cv::COLORMAP_JET);
    
            cv::imshow("image", image);
            cv::imshow("uhist", uhist);
            cv::imshow("vhist", vhist);
    
    
    
            if ((cv::waitKey(1)&255) == 'q')
                break;
        }
    
        return 0;
    }
    

* * *

[![enter image description
here](http://i.stack.imgur.com/fPvsg.png)](http://i.stack.imgur.com/fPvsg.png)
Figure 1: v-disparity

[![fake disparity
matrix](http://i.stack.imgur.com/YXYvf.png)](http://i.stack.imgur.com/YXYvf.png)
Figure 2: Fake disparity matrix

[![enter image description
here](http://i.stack.imgur.com/R0qSt.png)](http://i.stack.imgur.com/R0qSt.png)
Figure 3: u-disparity

* * *

  1. edit: 
     * correct name for u- and v-disparity and separate time measurement in c++ example
     * small typo


Answer: Today i had the possibility to reinvestigate the problem. Remembering the
OpenCV basics
([1](http://docs.opencv.org/2.4/doc/tutorials/core/how_to_scan_images/how_to_scan_images.html))
for the `Mat`-structure and the fact that only one calculation takes a huge
amount of time, i had the solution.

In OpenCV, each row of an image could be reached by a row-pointer. For
iterating columns (done in u-disparity calculation) i suspect, that OpenCV
needs to resolve every row-pointer + column-offset for building the histogram.

Changing the Code in a way, that OpenCV is able to use row-pointer, solves the
problem for me.

    
    
                | old code [s] | changed [s]
    ------------+--------------+-------------
    V-HIST-TIME | 0.00351909   | 0.00334152
    U-HIST-TIME | 0.600039     | 0.00449285
    

So for the u-hist-loop i transpose the image and reverse the operation after
the loop. The line wise access for calculation could now be done via the row-
pointer.

Changed Codelines:

    
    
            // === CALCULATE U-HIST ===
            image = image.t();
            for(int i = 0; i < IMAGE_WIDTH; i++)
            {
                tmpImageMat = image.row(i);
                uhist.col(i).copyTo(tmpHistMat);
    
                cv::calcHist(&tmpImageMat, 1, channels, cv::Mat(), tmpHistMat, 1, histSize, hist_ranges, true, false);
    
                uhist.col(i) = tmpHistMat / (float) IMAGE_WIDTH;
            }
            image = image.t();
    

* * *

Finally my second question takes effect, the runtime-issue belongs not to the
loop. A time less than 5 ms is (for now) fast enough.

