例えばcv::FindContoursとかした結果のstd::vector<cv::Rect>的なものを突っ込むと、前フレームとの差分を考慮して、同一オブジェクトと思われるものに共通のIDを振った結果を返してくれる。
同一オブジェクトとみなすスコアを計算する関数を用意すれば対象はなんでも良いので、使える場面はそこそこあるのではないかと思う。
記事のタグにはopenFrameworksを入れたが、Tracker自体はopenFrameworksに依存していないので取り出して使うこともできる。
結果的にはおそらくofxCv::Trackerの再実装に近い感じになったと思う。
コメントを入れつつ全文コピペする。
Tracker.h
// Copyright 2020 nariakiiwatani
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#pragma once
#include <vector>
#include <map>
#include "ofAppRunner.h"
// Trackeeにはトラッキングしたいオブジェクトの型を指定する。
// cv::Pointを追跡したければTracker<cv::Point>。
template<typename Trackee, typename Result = Trackee>
class Tracker
{
public:
using id_type = std::size_t;
using trackee_type = Trackee;
using result_type = Result;
protected:
id_type next_id_=0;
// トラッキング中のもののリスト。一時的にlostしているものも含む
std::map<id_type, Trackee> exists_;
// 一時的にlostしているもののリスト。第二要素はlostしている時間
std::map<id_type, float> absents_;
// lostしてからこの時間は一時的なlostであるとしてIDを残しておく
// 時間ではなくフレーム数で管理した方が良い場合もあるかも
float persistence_=1;
public:
// トラッキング関数の本体
void track(const std::vector<Trackee> &trackee) {
using namespace std;
// 初回のトラッキングか、もしくは前回のフレームで全オブジェクトが死んでいた場合、今回のインプットは全て採用する
if(exists_.empty()) {
for(auto &&p : trackee) {
exists_.insert(make_pair(next_id_++, newResult(p)));
}
return;
}
// 各exist_と各trackeeとの間のスコアを計算する
// 同一スコアのペアがあった場合にmapでは期待した動きをしないのでmultimap
// multimap<スコア, pair<exist_のid, trackeeのインデックス>>
multimap<float, pair<id_type, id_type>> score_map;
vector<id_type> unused_trackee;
for(int i = 0; i < trackee.size(); ++i) {
for(auto &&p : exists_) {
float score = calcIdentityScore(p.second, trackee[i]);
score_map.insert(make_pair(score, make_pair(p.first, i)));
}
// 既存のexist_のどれともペアになれなかったtrackeeを最後にexist_に追加するためのvector
unused_trackee.push_back(i);
}
// exists: このフレームに存在するIDのリスト
// absents: exists_にはあるが、このフレームに存在しないIDのリスト
std::vector<id_type> exists, absents;
// いったんexists_の全IDを存在しないことにしておいて、存在が確認できたやつを除外して残ったのが本当に存在しないやつ、という方針
for(auto &&p : exists_) {
absents.push_back(p.first);
}
// スコアマップを参照して処理していく
while(!score_map.empty()) {
// 未処理のスコアのうち、一番評価が高いものを取得
// map(multimap)はキーの昇順でソートしてくれるので最初のものが一番値が小さい つまり 評価が高い
auto primary = begin(score_map);
// exists_内のID
id_type id0 = primary->second.first;
// trackee内のインデックス
id_type id1 = primary->second.second;
// スコアが1以上であれば別オブジェクトと判断し、新規にIDを発行する
// 閾値が1なのは恣意的なので、virtual float getIdentityScoreThreshold()的な関数を作っておいた方が良いかもしれない
if(primary->first > 1) {
id0 = next_id_++;
exists_[id0] = newResult(trackee[id1]);
}
else {
updateResult(exists_[id0], trackee[id1]);
}
// このフレームでid0が存在することが確定したのでexistsにIDを保存し、absentsから削除
exists.push_back(id0);
// itという変数名を後でも使いたいがためにスコープを区切っている。
// 変数名を変えるのとどちらが可読性が高いかは知らない
{
auto it = find(begin(absents), end(absents), id0);
if(it != end(absents)) {
absents.erase(it);
}
}
// score_map内で、IDやインデックスのいずれかが被っているものを全て削除する
// これをやらないと、trackeeの要素が複数のexists_と同一と判定されることがある
// score_mapにinsertする時点で間引くこともできそうだが、煩雑になるので冗長だがここで削除する
for(auto it = begin(score_map); it != end(score_map);) {
if(it->second.first == id0 || it->second.second == id1) {
it = score_map.erase(it);
}
else {
++it;
}
}
// id1はusedなのでunusedリストから削除
unused_trackee.erase(find(begin(unused_trackee), end(unused_trackee), id1));
}
// unusedだったものを新たなオブジェクトとしてexist_に追加
for(auto &&id1 : unused_trackee) {
id_type id0 = next_id_++;
exists_[id0] = newResult(trackee[id1]);
}
// このフレームで存在していたIDを不在リストから削除
for(auto &&e : exists) {
absents_.erase(e);
}
// 不在リストを更新
// すでに存在するIDである場合にstd::map::insertは失敗してくれるので、
// 新要素は0で初期化され、既存要素は操作されない挙動になる。
for(auto &&a : absents) {
absents_.insert(make_pair(a, 0));
updateWhileAbsent(exists_[a]);
}
}
// 毎フレーム呼ばれる想定の処理。trackの最後に呼ぶようにしてもよかったかもしれない。
void update() {
using namespace std;
float frame_time = ofGetLastFrameTime();
for(auto it = begin(absents_); it != end(absents_);) {
if((it->second += frame_time) > persistence_) {
exists_.erase(it->first);
it = absents_.erase(it);
}
else {
++it;
}
}
}
int getNumTrackee() const { return exists_.size(); }
const std::map<id_type, Result>& getExists() const { return exists_; }
const std::map<id_type, float>& getAbsents() const { return absents_; }
float getPersistence() const { return persistence_; }
void setPersistence(float persistence) { persistence_ = persistence; }
protected:
virtual float calcIdentityScore(const Result &a, const Trackee &b)=0;
virtual Result newResult(const Trackee &t)=0;
virtual void updateResult(Result &dst, const Trackee &t)=0;
virtual void updateWhileAbsent(Result &dst){}
};
template<typename Trackee>
struct TrackeeInfo {
using trackee_type = Trackee;
// possible state list:=> exist(is_exist==true), lost(is_exist==false)
// additional flags:=>
// new_seen(first frame in exist but not for re-seen)
// seen(first frame in exist including re-seen)
// new_lost(first frame in lost including re-lost)
// new_dead(last frame of lost. this object is going to disappear in next frame)
bool is_exist;
bool is_new_seen;
bool is_seen;
bool is_new_lost;
bool is_dead;
// age:=> elapsed time after seen at first time. keeps counting up until it's lost.
float age;
// age_after_lost:=> elapsed time after lost. resets everytime it's lost.
float age_after_lost;
// object:=> trackee itself
Trackee object, object_prev;
TrackeeInfo() = default;
virtual void updateForNew(const Trackee &t) {
is_exist = true;
is_new_seen =
is_seen = true;
is_new_lost =
is_dead = false;
age =
age_after_lost = 0;
object =
object_prev = t;
}
virtual void updateForExist(float elapsed_time, const Trackee &t) {
is_seen = !is_exist;
is_exist = true;
is_new_seen =
is_new_lost =
is_dead = false;
age += elapsed_time;
age_after_lost = 0;
object_prev = object;
object = t;
}
virtual void updateForLost(float elapsed_time, const Trackee &t) {
is_new_lost = is_exist;
is_exist =
is_new_seen =
is_seen =
is_dead = false;
age += elapsed_time;
age_after_lost += elapsed_time;
object_prev = object;
object = t;
}
};
// Trackerと合わせて使うことで、各トラッキングオブジェクトの存在時間やlostした瞬間、deadした瞬間などを知ることができる
template<typename Tracker, typename Info = TrackeeInfo<typename Tracker::trackee_type>>
class TrackerAdditionalInfo
{
public:
using info_type = Info;
// Trackerのupdateの後に毎回この処理を呼ぶと、追加の情報を生成してくれる
void update(const Tracker &tracker) {
using namespace std;
for(auto it = begin(info_); it != end(info_);) {
// deadフラグが立っているものを削除
if(it->second.is_dead) {
it = info_.erase(it);
}
else {
it->second.is_dead = true;
++it;
}
}
float frame_time = ofGetLastFrameTime();
auto exists = tracker.getExists();
auto absents = tracker.getAbsents();
for(auto &&obj : exists) {
auto found = info_.find(obj.first);
// 新規オブジェクトだったら
if(found == end(info_)) {
Info info;
info.updateForNew(obj.second);
// 今気づいたけど、findした後にinsertしてるの無駄だった。
// いきなりinsertして戻り値の成功フラグをみるのが正解だと思います
info_.insert(make_pair(obj.first, info));
}
// 存在するオブジェクトだったら
else if(absents.find(obj.first) == end(absents)) {
found->second.updateForExist(frame_time, obj.second);
}
// lostしたまたはしているオブジェクトだったら
else {
found->second.updateForLost(frame_time, obj.second);
}
}
}
const std::map<typename Tracker::id_type, Info>& getInfo() const { return info_; }
private:
std::map<typename Tracker::id_type, Info> info_;
};
// 例えばofRectangleをトラッキングしたい場合はこのようなクラスを作成すると良い
// Trackerを継承してcalcIdentityScoreを実装するだけでOK
class RectTracker : public Tracker<ofRectangle>
{
protected:
// この例の場合、位置とサイズをそれぞれスコア化して悪い方を採用している
float calcIdentityScore(const result_type &a, const trackee_type &b) {
using namespace std;
float position_distance = glm::distance(a.getCenter(), b.getCenter());
float position_score = position_threshold_ == 0
? position_distance == 0 ? 0 : 1
: ofMap(position_distance, 0, position_threshold_, 0, 1, false);
float size_distance = max(abs(a.getWidth()-b.getWidth()), abs(a.getHeight()-b.getHeight()));
float size_score = size_threshold_ == 0
? size_distance == 0 ? 0 : 1
: ofMap(size_distance, 0, size_threshold_, 0, 1, false);
return max(position_score, size_score);
};
result_type newResult(const trackee_type &t) { return t; }
void updateResult(result_type &dst, const trackee_type &t) { dst = t; }
protected:
float position_threshold_=100;
float size_threshold_=100;
};