2014년 10월 27일 월요일

Real-Time Object Tracker in C++(카메라를 이용한 물건추적)

blobs_demo.zip


Contents

Introduction

This article is about tracking moving or static objects with a conventional web cam at real-time speed. A simple way of tracking is to compare a predefined background image with the same background frame when objects start to appear. This scenario is applicable in static surroundings where you can learn the background image without any foreground articles you'd expect to track (e.g., indoors, landings, offices, shops, warehouses etc...). In the case that an article moves and remains static for a prolonged period of time in the scene, you may consider it as becoming the part of the scene now, and superimpose its image to the background to avoid further detections. The same is applicable if some background item is removed from the scene. The drawbacks of this approach include illumination or cam position change. In that case, you will have to estimate the new background again. Another solution is to use edge operators to avoid illumination specific changes. But you will need additional code to devise if you'd like to identify the object's body and not just its outline.
The conventional web cam 640x480 resolution is far redundant. You may downscale it about three times to remove the noise usually present and significantly boost the speed of processing without essential loss of tracking abilities, unless you expect to track very minute objects. The downscaling step allows to achieve great processing speeds in object tracking. It runs about 100fps on a 2Ghz single core when no objects are present, and from 30 to 90fps when there are. The bigger the object, the more time is required to estimate all pixels belonging to the blob.

Background

The article and code are based on my previous submissions, except theImageBlobs class. You should have a look at the following articles if you have questions about the GUI interface or particular code fragments:
The GUI is targeted at 640x480 web cams, and if you want to use it for different resolutions, have a look at the Face Detection article to add the required changes. You can not expect me to provide you a complete application for every custom video device.

Using the code

Setup the camera and frames capture rate as described in Video Preview and Frames Capture to Memory with SampleGrabber in Buffered Mode and start video capture. Click the background radio box to start the background estimation process first. All the captured frames will be added together, and the mean background frame will be estimated and saved to a JPEG file,background.jpg, once you have clicked the start tracking radio box to start object tracking. I suggest you point your camera to some place where you can expect moving objects. Estimate the background for about several seconds to cope with camera noise or some casual moving articles appearing in the scene for short periods of time. The mean background estimate will effectively remove them. Now, introduce the objects to the scene you want to track, or wait for them to appear there if they are alive.

The library

The mean estimate of the background frame is advisable as it allows to filter out any noise or tiny movements.
 Collapse Copy Code
1: background[i] = 0;
   frames_number = 0;
2: while(frames_number < N)
       background[i] = current_frame[i] + background[i];
       frames_number++;
3: background[i] = background[i] / frames_number;
The new classes in the library are:
  • MotionDetector
  • ImageBlobs
The changes in the MotionDetector allow to set the background frame to which the comparison will be done with every new image frame, rather than taking the difference between consecutive frames as in the Face Detection article. The background frame and the new image frame are presented with ImageResizeobjects.
First, you need to initialize the MotionDetector object with the video frame width, height, and downscaling factor:
  • void MotionDetector::init(unsigned int image_width, unsigned intimage_height, float zoom);
To downscale the image three times, use zoom = 0.125f.
Invoke the set_background() function once you finish the background estimation process:
 Collapse Copy Code
inline int MotionDetector::set_background(const unsigned char* pBGR)
{        
    return m_background.resize(pBGR);
}
Now, you may call the detect() function to estimate the pixels belonging to the foreground objects:
 Collapse Copy Code
const vec2Dc* MotionDetector::detect(const unsigned char* pBGR)
{
    if (status() < 0)
            return 0;
    
    m_image.resize(pBGR);

    //RGB version
    char** r1 = m_image.getr();
    char** g1 = m_image.getg();
    char** b1 = m_image.getb();
    char** r2 = m_background.getr();
    char** g2 = m_background.getg();
    char** b2 = m_background.getb();
    for (unsigned int y = 0; y < m_motion_vector->height(); y++) {
            for (unsigned int x = 0; x < m_motion_vector->width(); x++) {
                    if (abs(r1[y][x] - r2[y][x]) > m_TH ||
                        abs(g1[y][x] - g2[y][x]) > m_TH ||
                        abs(b1[y][x] - b2[y][x]) > m_TH)
                            (*m_motion_vector)(y, x) = 1;
                    else
                            (*m_motion_vector)(y, x) = 0;
            }
    }

    //gray scale version
    /*m_difference_vector->sub(*m_image.gety(), *m_background.gety());
    for (unsigned int y = 0; y < m_motion_vector->height(); y++) {
            for (unsigned int x = 0; x < m_motion_vector->width(); x++) {
                    if (fabs((*m_difference_vector)(y, x)) > m_TH)
                            (*m_motion_vector)(y, x) = 1;
                    else
                            (*m_motion_vector)(y, x) = 0;
            }
    }*/

    m_tmp_motion_vector->dilate(*m_motion_vector, 3, 3);
    m_motion_vector->erode(*m_tmp_motion_vector, 5, 5);
    m_tmp_motion_vector->dilate(*m_motion_vector, 3, 3);

    return m_tmp_motion_vector;
}
You may use either RGB values comparison or gray image data. The latter, I found not robust for similar looking colors when converted to gray values. The dilation and erosion operators allow to fill any gaps in the object's blobs that might appear due to similar pixel colors of the background and the object, and remove the noise of some tiny movements or very thin objects.
The returned vector is used for blobs extraction with the ImageBlobs object. You will need the following functions to use the class:
  • void ImageBlobs::init(unsigned int width, unsigned int height);
  • int ImageBlobs::find_blobs(const vec2Dc& image, unsigned intmin_elements_per_blob = 0);
  • void ImageBlobs::find_bounding_boxes();
  • void ImageBlobs::delete_blobs();
First, you need to initialize the object to the downscaled image width and height (e.g., init(zoom * image_width, zoom * image_height)). Then, you may proceed estimating blobs with find_blobs() on the image returned from theMotionDetector::detect() function call. The function searches for non-zero elements in the image vector adjoining horizontally or vertically, forming a blob. Then, it marks every element with the current found blob number.
For example, the 10x10 vector used as image vector:
 Collapse Copy Code
1 1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
0 1 0 0 0 1 1 1 1 0
0 0 0 0 1 1 1 1 1 0
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
find_blobs() will estimate three blobs from that image. You may get the vector containing the found blobs with the const vec2Dc* ImageBlobs::get_image()const function.
 Collapse Copy Code
1 1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
0 1 0 0 0 2 2 2 2 0
0 0 0 0 2 2 2 2 2 0
3 3 0 2 2 2 2 2 2 2
3 3 0 2 2 2 2 2 2 2
3 0 2 2 2 2 2 2 2 2
0 0 0 2 2 2 2 2 2 2
With min_elements_per_blob, you may discard small blobs from being detected (e.g., min_elements_per_blob = 5 will leave the third blob undetected).
To access the elements of the found blobs, you may use the following functions:
  • inline unsigned int ImageBlobs::get_blobs_number() const;
  • inline const struct Blob* ImageBlobs::get_blob(unsigned int i) const;
The blob is returned in the Blob structure:
 Collapse Copy Code
struct Blob {
    unsigned int elements_number;
    vector<struct Element> elements;
    unsigned int area;
    RECT bounding_box;      //[top,left; right,bottom)    
};
where elements_number is the number of elements in the blob contained in theelements array of Element structures.
 Collapse Copy Code
struct Element {
    vector<struct Element> neighbs;
    struct Coord coord;        
};
The neighbs contain the directly adjoining neighboring elements, and coord is the element coordinate in the image vector.
 Collapse Copy Code
struct Coord {
    int x;
    int y;
};
After you call find_blobs(), you may optionally invoke find_bounding_boxes() to estimate the bounding boxes of all blobs found to Blobs::bounding_boxwindow's RECT structure. Before the next call to find_blobs(), you need to delete the found blobs from the ImageBlobs object with delete_blobs().
The find_blobs() function is shown below:
 Collapse Copy Code
int ImageBlobs::find_blobs(const vec2Dc& image, 
                           unsigned int min_elements_per_blob)
{
        if (m_image == 0)
        //not initialized
            return -1;
        
        m_image->copy(image);        

        while (true) {
            struct Blob blob; 
            blob.elements_number = 0;
            blob.area = 0;

            unsigned int y, x;
            //find first non-zero entry//////////////////////////////////
            for (y = 0; y < m_image->height(); y++) {
                for (x = 0; x < m_image->width(); x++) {
                    if ((*m_image)(y, x) != 0) {
                        struct Element element;
                        element.coord.x = x;
                        element.coord.y = y;
                        blob.elements_number = 1;
                        blob.elements.push_back(element);
                        blob.area = 0;
                        memset(&blob.bounding_box, 0, sizeof(RECT));
                        break;
                    }
                }
                if (blob.elements_number > 0)
                        break;
            }

            if (blob.elements_number == 0) {
                mark_blobs_on_image();
                return get_blobs_number();
            }

            blob.elements.reserve(m_image->width() * m_image->height());
            //find blob//////////////////////////////////////////////////
            unsigned int index = 0;
            while (index < blob.elements_number) {
                unsigned int N = (unsigned int)blob.elements_number;
                for (unsigned int i = index; i < N; i++) {
                    add_up_neighbour(blob, i);
                    add_right_neighbour(blob, i);
                    add_down_neighbour(blob, i);
                    add_left_neighbour(blob, i);
                }
                index = N;
            }
            remove_blob_from_image(blob);

            if (blob.elements_number > min_elements_per_blob) {
                blob.area = (unsigned int)blob.elements_number;
                blob.elements.reserve(blob.elements_number);
                m_blobs.push_back(blob);
            }                
    }        
}
The add_*_neighbour() functions check for the directly adjoining image element from above, below, left, or right from the ith Element in the current blob and adds it to the Blob elements array:
 Collapse Copy Code
inline unsigned int ImageBlobs::add_up_neighbour(struct Blob& blob, unsigned int i)
{
    const struct Element& element = blob.elements[i];
    if (element.coord.y - 1 < 0)
        return 0;
    else if ((*m_image)(element.coord.y - 1, element.coord.x) > 0) {
        struct Element new_element;
        new_element.coord.x = element.coord.x;
        new_element.coord.y = element.coord.y - 1;
        if (has_neighbour(element, new_element) == false) { 
            int index = is_element_present(blob, new_element);
            if (index >= 0) {
                blob.elements[index].neighbs.push_back(element);
                return 0;
            }
            new_element.neighbs.push_back(element);
            blob.elements_number++;
            blob.elements.push_back(new_element);
            return 1;
        }
        else
                return 0;
    }
    else 
        return 0;
}
has_neighbour() and is_element_present determine if the new element is already present in the blob:
 Collapse Copy Code
inline int ImageBlobs::is_element_present(const struct Blob& blob, 
           const struct Element& new_element) const
{
    //int index = 0;
    for(int i = (int)blob.elements_number - 1; i >= 0; i--) {
        const struct Element& element = blob.elements[i];
        if (element.coord.x == new_element.coord.x &&
            element.coord.y == new_element.coord.y) {
                //wprintf(L" %d\n", blob.elements_number - 1 - i);
                return i;
        }
        //if (++index > 2)  //inspect at least 2 last elements
        //        break;
    }
    return -1;
}

inline bool ImageBlobs::has_neighbour(const struct Element& element, 
            const struct Element& new_element) const
{
    unsigned int N = (unsigned int)element.neighbs.size();
    if (N > 0) {
        for (unsigned int i = 0; i < N; i++) {
            if (element.neighbs[i].coord.x == new_element.coord.x &&
                element.neighbs[i].coord.y == new_element.coord.y) 
                return true;
        }
        return false;
    }
    else
        return false;
}

Results

Here, I have selected a static background and performed some object tracking experiments with the objects at hand. The background I used is depicted below. It was averaged over a period of several seconds.
The next two objects (an LCD-TFT screen cleaner and mobile phone) are tracked at 66.67fps.
The mobile phone power adaptor is tracked at 71.43fps. You see the cord is not detected due to erosion and dilation operators, as it is quite thin.
Now, some pens and keys: 90.91fps.
A more complex scenario: three different objects detected at 29.41fps.
Jimi Hendrix (the Are You Experienced album, very good sound) and 9v batteries at 55.56fps.
The other background setup:
Several 9v batteries and a roll on the carpet detected at 90.91fps. You see one battery is left undetected due to the minimum number of elements limit.
Power adaptor, LCD-TFT cleaner, and 9v batteries detected at 90.91fps. The tiny ones are left undetected again, but this time due to erosion and dilation operators.
Next, some candle and mobiles at 83.33fps.
Now, as you can see, the bigger the size of the object, the more time is required to estimate the elements of the blobs. Also, it does not handle the shadows cast by objects on the white back wall and on the table. However, more pronounced shadows will be tracked as pertaining to the object.

Points of interest

You may extend the algorithm to monitor an object's bounding box positions. In case they will be static for a specified amount of time, you may add that region to the background scene image. Thus, the object becomes part of the scene (e.g., some object moved to the scene and remaining static).

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPL)

About the Author

Chesnokov Yuriy



Mvp
Former Cambridge University post-doc (http://www-ucc.ch.cam.ac.uk/research/yc274-research.html) currently lives in Krasnodar, Russia and doing some contract research for third parties. Research intrests in digital signal processing in medicine, image and video processing, pattern recognition, AI methods, computer vision. Also in English, Español, Italiano languages. You may approach me for the code/research development in the above areas chesnokov.yuriy@gmail.com.

Publications:

Complexity and spectral analysis of the heart rate variability dynamics for distant prediction of paroxysmal atrial fibrillation with artificial intelligence methods. Artificial Intelligence in Medicine. 2008. V43/2. PP. 151-165 (http://dx.doi.org/10.1016/j.artmed.2008.03.009)

Face Detection C++ Library with Skin and Motion Analysis. Biometrics AIA 2007 TTS. 22 November 2007, Moscow, Russia. (http://www.dancom.ru/rus/AIA/2007TTS/ProgramAIA2007TTS.html)

Screening Patients with Paroxysmal Atrial Fibrillation (PAF) from Non-PAF Heart Rhythm Using HRV Data Analysis. Computers in Cardiology 2007. V. 34. PP. 459–463 (http://www.cinc.org/Proceedings/2007/pdf/0459.pdf)

Distant Prediction of Paroxysmal Atrial Fibrillation Using HRV Data Analysis. Computers in Cardiology 2007. V. 34. PP. 455-459 (http://www.cinc.org/Proceedings/2007/pdf/0455.pdf)

Individually Adaptable Automatic QT Detector. Computers in Cardiology 2006. V. 33. PP. 337-341 http://www.cinc.org/Proceedings/2006/pdf/0337.pdf)


Past/recent outsourcing code/research:

www.bitcycle.com - AI consulting
www.cit.ie - augmented reality C++
www.apniecare.com - ECG processing C++/C#
confidential Japanese company - face recognition C/MATLAB
confidential company in Australia - video capture C#/DirectShow
www.system7.co.uk - CBIR C#/ASP.NET (cbir.system7.com)
confidential enterprise in UK - pedestrian detection C++/CLI
www.trulyintelligent.com - AI consulting
www.devline.ru - video codecs C++
Occupation:Software Developer
Company:Confidential Japanese firm (face recognition)
Location:Russian Federation Russian Federati

댓글 없음: