We should implement multithreaded DETECT_PERIODICALLY

[ayberkozgur]

We agree that there should be 3 ways to use Chilitags:

1. Detect all the time, simplest.
2. Detect and track all the time, takes more time, more robust, OK.
3. Detect periodically.

Now, the current periodic detection is "1 call detect, 14 calls track, and so on". This must run on the same thread on the user side as the user cannot determine whether Chilitags will be tracking or detecting (without counting the frames manually or calling with TRACK_ONLY and DETECT_ONLY, but neither is the point of DETECT_PERIODICALLY; and this wouldn't be thread safe without appropriate locks). As these run in the same thread, detection delays the pose update of tags significantly; assume that detection takes 200 ms while tracking takes 15 ms. A 200 ms call every half a second causes hiccups even if the visual camera image update is running on another thread.

Now, assume that detection and tracking run on separate threads, once one detect cycle is sacrificed, Chilitags can run at 30 FPS since the detect cycle can catch up with the track cycle.

The easiest way to do this is to launch an additional "detection" thread when Chilitags is created. During a normal Chilitags3D::estimate() call, the frame is copied for the use of tracking and detection. The detection thread, having a new frame, updates the "detected" tag poses as soon as it can. Meanwhile, the Chilitags3D::estimate() call, after copying the frame, takes the most recent detected tag poses and uses it to track and return the results. I'm assuming that we place mutexes where necessary.

At this point, we have alternatives to choose from for various performance presets:

• Run detection every N frames completed of tracking, if possible; and as long as there's a new camera frame
• Run detection as frequently as possible, as long as there's a new camera frame

In short, I see no "correct" way of implementing DETECT_PERIODICALLY without at least 1 additional thread. The above implementation can be done with pthreads for cross-platform compatibility.

Or, another solution might be to remove DETECT_PERIODICALLY altogether, lock the appropriate members (such as image buffers and tag poses) across calls to estimate() with mutexes and expect the user to implement periodic detection with DETECT_ONLY and TRACK_ONLY.

What do you think?

[ayberkozgur]

The same issue is relevant for Chilitrack: https://github.com/chili-epfl/chilitrack/issues/5

[qbonnard]

Not really relevant: I was thinking about a 4th way to use chilitags relative to tracking: detect in a sliding window, track everywhere. That's another detection/tracking mix, which does not has the hiccups problem.

So, regarding multithreading, here is my thinking. First, I think it should be done at the 2D level, the 3D interface is merely a wrapper for the detection results.

Detection and Tracking are loosely coupled I think, so we would get thread safety for pretty cheap, if not free. Since the various parts of Chilitags are functors, I'd rather rely on copying results than on locks.

Also, since we're using c++11, we could use all the fun stuff in #include <thread>, mostly futures. It seems that something as simple as taht could do:

map<int, Quad> find(Mat inputImage, DetectionTrigger trigger) {
    if (trigger == DETECT_PARALLEL) {
        //mFutureTags is a std::future<map<int,Quad>>
        if (mFutureTags.valid()) {
            //We got a result from the parallel detection
            auto tags = mFutureDetection.get();

            // sync detection and tracking
            mTrack.update(mFutureInputImage, tags);

            //start a new parallel detection
            mFutureTags = std::async(std::launch::async, [](){
                return find(mFutureInputImage, DETECT_ONLY);
            });
            // keep track of the input of the parrallel detection
            mFutureInputImage = inputImage; //I think cv::Mat is thread safe enough

            return tags;
        } else {
            // detection is still running in parallel, fall back to tracking
            return find(inputImage, TRACK_ONLY);
        }
    }

    // Rest of current Chilitags::find() body
}

Disclaimer: I never actually used #include <thread>, so this may be pure fantasy. Still, all variables with "Future" in their name are pretty cool.

How does it sound ?

[ayberkozgur]

I think the sliding window method corresponds exactly to the "detect as frequently as possible in another thread" method I mentioned above.

About std threads, I think we should stick to pthreads, they are more mature, stable and cross-platform. See http://stackoverflow.com/questions/13134186/c11-stdthreads-vs-posix-threads. I really couldn't afford any kind of thread issue on Android.

[qbonnard]

I don't think I was clear on the sliding window thing. I meant a spatial window, e.g. the top left quadrant of the input image, then the top right, then bottom left, then the bottom right, then a scaled down version. That would give a through put about 4 times faster, constant processing time, and a latency of 5 frames.

[qbonnard]

I don't think I was clear on the sliding window thing. I meant a spatial window, e.g. the top left quadrant of the input image, then the top right, then bottom left, then the bottom right, then a scaled down version. That would give a constant processing time about 4 times faster, and a latency of 5 frames. Of course, other factors than 4 are possible...

[ayberkozgur]

@qbonnard it sounds interesting but we would have to take care such that tags that cross the borders of windows are detected. But the real problem is, in order to increase the throughput to x4, we would have to parallelize detection completely in 4 independent parts, such as spatial parallelization as you suggested. There are 2 issues: For one, there are many things that can run alongside chilitags, invading the machine with detection threads might not be a good idea. Second, this issue is really about the parallelization of detection, I don't think it prevents us from separating the detection thread, which is the focus of this issue.

[severin-lemaignan]

@qbonnard I like your idea a lot. It would 'smoothens' a lot the TRACK and DETECT strategy, and could become a nice default behaviour. @ayberkozgur I agree with you, this idea is off-topic for this issue. Quentin, could you open a separate issue? Regarding tags crossing the borders, it's not a big issue if you use an overlapping sliding window.

[qbonnard]

I was sure I already wrote that in some issue... But couldn't find it, so here it is: https://github.com/chili-epfl/chilitags/issues/66

[qbonnard]

@ayberkozgur regarding pthread, is it still the case these days that C++11 are unstable ? How does pthread work with windows people ?

[ayberkozgur]

It (supposedly) doesn't work on Android. I have no idea about Windows.

[qbonnard]

Yay standards. Then I'd rather aim for an integration of multithreading as a sample, e.g. multithreaded-detection-linux.cpp, multithreaded-detection-windows.cpp, multithreaded-detection-android.cpp, multithreaded-detection-qt.cpp, or what not, than in the core of chilitags, if we can't rely on standards.

In this direction, we could expose the Track class (or encapsulate its functionality into a static Chilitags::track(inputImage, previousTags)) to let the users handle multithreading as they see fit. What do you think ?

[ayberkozgur]

Whoops I think I made a wrong statement there. Pthreads work seamlessly for linux and android (and most probably windows). It's the c++11 threads that don't work for android. I think we're better off hiding the backgroud detection functionality within chilitags instead of letting the user worry about them. It would be really nice to have one API call that just works and is fast out of the box.

[qbonnard]

That's what I understood ;) I suspect that the P in pthread only means pain for Windows. Standard threads are not standard enough for android, and threads are a bad idea with emscripten. It looks like the "just work out of the box" is not for a near future, is it ? Anyway, at least for prototyping multithreads, it's probbly easier to separate Track and Chilitags for now.

[ayberkozgur]

I think pthreads are pretty much the standard and can be relied upon at this point for any platform that is listed to support them.

[qbonnard]

Implemented in #72