用于通过设备查找遗漏数据捕获的算法

Question

我们有4个摄像头“ CAMA”，“ CAMB”，“ CAMC”，“ CAMD”，沿着道路和此序列安装了每个路口。交通流量是这样的“ CAMA”，而“ CAMD”在最后。

        |      |        |      |        |      |        |    |
--------        --------        --------        --------      -------
===>      camA            camB            camC            camD
---------------------------------------------------------------------

每当车辆通过路口或在交界处转弯时，相机都会放置以记录车牌号。工作摄像头大部分时间都会捕获盘子号，但是当它在过去的N车中错过一定的汽车时，我们认为这是一个“不良”相机。

例如，如果带有板“ Platealice”的汽车在不转动的情况下向前驾驶，第二辆带板“ plateTom”在“ CAMC”交界处进行转动，我们将记录捕获的记录：

{
    "camA":[
        (1655529900, "plateAlice"),
        (1655530010, "plateTom"),
    ],
    "camB":[
        (1655529920, "plateAlice"),
        (1655530020, "plateTom"),
    ],
    "camC":[
        (1655529970, "plateAlice"),
        (1655530050, "plateTom"),
    ],
    "camD":[
        (1655529980, "plateAlice"),
    ]
}

有没有办法从所有4个相机中获取过去的X记录并确定何时摄像机变坏？例如，如果相机错过了过去10辆汽车中的5辆，我们将其视为不良的相机。

假设

1. 多个摄像机可能很糟糕，但是至少有1个相机总是在起作用。
2. 车辆可以再次返回“ CAMA”，因此车辆返回时可以通过相机多次记录板号。
3. 只有当相机记录了板号（奇怪的假设来简化事物）

Python解决方案的首选时，只有车辆才能在交界处转弯，我在下面的python中进行了无工作的尝试。谢谢！

---

我在Python中的非工作尝试：

from collections import namedtuple

Record = namedtuple("record", ["time", "plate"])


# 10 vehicles (counting repeated vehicles that circle back again)
data = {
    "camA":[
        Record(1655530000, "plateAlice"),
        Record(1655530110, "plateTom"),
        Record(1655530210, "plateMissing"),
        Record(1655530310, "plateCharlie"),
        Record(1655530410, "plateDan"),
        Record(1655530510, "plateEdward"),
        Record(1655530610, "plateMissing"), # looped back for a 2nd time
        Record(1655530700, "plateAlice"), # looped back for a 2nd time
        Record(1655530800, "plateAlice"), # looped back for a 3rd time
        # missing "plateTom" (looped back for a 2nd time) because bad camera
        # missing "plateFrank" because bad camera
    ],
    "camB":[
        Record(1655530020, "plateAlice"),
        Record(1655530120, "plateTom"),
        # missing "plateMissing" because bad camera
        # missing "plateCharlie" because bad camera
        # missing "plateDan" because bad camera
        # missing "plateEdward" because bad camera
        Record(1655530620, "plateMissing"),
        # missing "plateAlice" because bad camera
        Record(1655530820, "plateAlice"), 
        # missing "plateFrank" because bad camera
    ],
    "camC":[
        Record(1655530070, "plateAlice"),
        Record(1655530150, "plateTom"),   # Makes a turn at this junction
        Record(1655530230, "plateMissing"),
        Record(1655530330, "plateCharlie"),
        Record(1655530430, "plateDan"),
        Record(1655530530, "plateEdward"),
        Record(1655530630, "plateMissing"),
        Record(1655530730, "plateAlice"), 
        Record(1655530830, "plateAlice"), 
        Record(1655530930, "plateTom"), # looped back for a 2nd time
        Record(1655530930, "plateFrank"),   # Makes a turn at this junction
    ],
    "camD":[
        Record(1655530080, "plateAlice"),
        # missing "plateTom" because it turned at "camC"
        Record(1655530240, "plateMissing"),
        Record(1655530340, "plateCharlie"),
        Record(1655530440, "plateDan"),
        # missing "plateEdward" because bad camera
        Record(1655530640, "plateMissing"),
        Record(1655530740, "plateAlice"), 
        Record(1655530840, "plateAlice"), 
        Record(1655530940, "plateTom"), # looped back for a 2nd time
    ]
}

def is_first_cam(cam):
    return cam == "camA"

def check_for_bad_cameras(data):
    misses = {
        "camA": 0,
        "camB": 0,
        "camC": 0,
        "camD": 0,
    }
    
    for r in data["camA"][::-1]:
        for i, cam in enumerate(data):
            if not is_first_cam(cam):
                for s in data[cam][::-1]:
                    if s.time > r.time and s.plate == r.plate:
                        break
                else:
                    misses[cam] += 1
        
    print(misses)   
    # Expected {'camA': 2, 'camB': 6, 'camC': 0, 'camD': 1}
    # Obtained {'camA': 0, 'camB': 3, 'camC': 0, 'camD': 1}
    
    
check_for_bad_cameras(data)

Answer 1

摄像机应在ABCD，ABC，AB或A中看到板。

注意：缺少D是看不见的，因为它等效于C的关闭。

from collections import namedtuple, defaultdict
from heapq import merge


Record = namedtuple("record", ["time", "plate"])


# data from your example.
# data = ... # Later CPythons key order preservation assumed.

cam2idx = {cam: i for i, cam in enumerate(data)}  # order cams should appear
idx2cam = {i: cam for i, cam in enumerate(data)}
last_idx = defaultdict(lambda :-1)
time_plate_cam = [[(rec.time, rec.plate, cam) for rec in records]
                  for cam, records in data.items()]
for time, plate, cam in merge(*time_plate_cam):  # sort by time
    idx = cam2idx[cam]
    prev = last_idx[plate]
    if idx != prev + 1 and idx != 0:
        print(f"{time}: {plate} appears suddenly at {cam} "
              f"missing {idx2cam[idx-1]}")
    last_idx[plate] = idx

结果：

1655530230: plateMissing appears suddenly at camC missing camB
1655530330: plateCharlie appears suddenly at camC missing camB
1655530430: plateDan appears suddenly at camC missing camB
1655530530: plateEdward appears suddenly at camC missing camB
1655530730: plateAlice appears suddenly at camC missing camB
1655530930: plateTom appears suddenly at camC missing camB
1655530930: plateFrank appears suddenly at camC missing camB