جمع ناحیهٔ تصویر با جدول پیشوند؛ چهار گوشه، مرز نیمه‌باز و آزمون مستقل

وقتی از یک تصویر ثابت، جمع شدتِ چند ناحیهٔ مستطیلی را می‌خواهیم، پیمایش دوبارهٔ همهٔ خانه‌های هر ناحیه تنها راه نیست. می‌توان ابتدا جدول جمعِ پیشوند ساخت و سپس پاسخ را از گوشه‌های آن بازیابی کرد. این درس، قرارداد اندیس‌ها و هزینهٔ این انتخاب را با شبکهٔ کوچکِ تألیفی بررسی می‌کند. داده‌ها ساختگی‌اند؛ دوربین، تشخیص عیب، مدل هوش مصنوعی و زمان پاسخ محصول آزمایش نمی‌شوند.

۱. قرارداد تصویر و مستطیل نیمه‌باز را تثبیت کنیم

تصویر، tuple سطرها و هر سطر نیز tuple است؛ هر بُعد از یک تا شانزده و هر شدت، int دقیقِ صفر تا ۲۵۵ است. bool، شناور، سطر خالی، شکل نامنظم و فهرست رد می‌شوند. این محدودیت‌ها قرارداد همین تمرین‌اند. مقدار شدت کد دیجیتالِ بی‌واحد است؛ از آن، توان نور، ولتاژ حسگر یا کیفیت قطعه نتیجه نمی‌گیریم.

نمونه سه سطر و چهار ستون دارد: سطر نخست دو، یک، چهار، صفر؛ سطر دوم سه، پنج، صفر، دو؛ سطر سوم یک، صفر، شش، یک. شمارهٔ سطر و ستون از صفر آغاز می‌شود. مختصات را به‌ترتیب آغاز سطر، پایان سطر، آغاز ستون و پایان ستون می‌دهیم. این ترتیب با زوجِ هندسیِ x و y یکی فرض نمی‌شود.

مستطیل نیمه‌باز است: آغاز داخل و پایان خارجِ انتخاب است. بنابراین سطرهای یک تا پیش از سه و ستون‌های یک تا پیش از چهار، شش خانه دارند. مرزها باید داخل قاب و مرتب باشند؛ درخواستِ بیرون قاب یا وارونه خطا می‌دهد. تقاطع خودکار، جابه‌جا کردن گوشه‌ها و پرکردن بیرون تصویر در این تابع وجود ندارد.

اگر آغاز و پایانِ یکی از محورها برابر باشند، ناحیه خالی و جمع آن صفر است. این تصمیم برای عمل جمع طبیعی است، ولی میانگینِ همان ناحیه را تعریف نمی‌کند؛ مساحت صفر است و نباید بر آن تقسیم کرد. ساختار خروجی فقط جمع را نگه می‌دارد و هیچ میانگین یا مساحت فیزیکی را به‌صورت ضمنی گزارش نمی‌کند.

۲. جدول پیشوند را با سطر و ستون صفر بسازیم

خانهٔ جدول در سطر r و ستون c، جمعِ پیکسل‌های دارای شمارهٔ سطر کوچک‌تر از r و شمارهٔ ستون کوچک‌تر از c است. پس سطر صفر و ستون صفرِ جدول، همگی صفرند. برای تصویر با ارتفاع H و عرض W، جدول H+1 سطر و W+1 ستون دارد. این حاشیه، دادهٔ بیرون تصویر یا گسترش مرزیِ فیلتر نیست؛ نمایشِ پیشوندِ خالی است.

تعریف integral در OpenCV 4.13.0، جمعِ پیش از مختصات و اندازهٔ یک‌خانه‌بزرگ‌تر را توضیح می‌دهد. در کدِ تألیفی، نام سطر و ستون را صریح نگه می‌داریم. خودِ OpenCV اجرا نشده است؛ انواع داده، چندکاناله بودن، مجموع مربع‌ها و مستطیل چرخیدهٔ آن API جزو این پیاده‌سازی نیستند.

برای ساخت، در هر سطر یک جمعِ جاری از چپ داریم و آن را با پیشوندِ بالایی جمع می‌کنیم. جدول نمونه چهار سطر دارد: پنج صفر؛ سپس صفر، دو، سه، هفت، هفت؛ سپس صفر، پنج، یازده، پانزده، هفده؛ و سرانجام صفر، شش، دوازده، بیست‌ودو، بیست‌وپنج. جدولِ کامل در خروجی کد هم ثبت می‌شود تا اشتباهِ انتقال یک خانه پنهان نماند.

نامِ «تصویر انتگرالی» به معنی یک قراردادِ اندیس یگانه نیست. مستندات integral_image در scikit-image 0.26.0 جدول هم‌اندازهٔ ورودی با جمعِ شاملِ خودِ خانه را تعریف می‌کند؛ integrate نیز انتهای شامل دارد. اینجا هیچ‌یک اجرا نشده‌اند. انتقال فرمولِ ما به جدولِ آن‌ها بدون تبدیل قرارداد، خطای مرزی می‌سازد.

۳. جمع ناحیه را با چهار گوشه بازیابی کنیم

برای ناحیهٔ سطرهای r0 تا پیش از r1 و ستون‌های c0 تا پیش از c1، از پیشوندِ پایینِ راست شروع می‌کنیم. نوارِ بالای ناحیه و نوارِ چپ را کم می‌کنیم؛ اشتراکِ بالای چپ دوبار کم شده است، پس یک بار آن را برمی‌گردانیم. رابطه در کد به‌ترتیب پایین راست منهای بالا راست منهای پایین چپ به‌علاوهٔ بالا چپ نوشته شده است.

در نمونهٔ شش‌خانه‌ای، چهار مقدارِ جدول بیست‌وپنج، هفت، شش و دو هستند. حسابِ بیست‌وپنج منهای هفت منهای شش به‌علاوهٔ دو، چهارده می‌دهد. جمعِ مستقیمِ پنج، صفر، دو، صفر، شش و یک نیز چهارده است. مقدارِ گوشهٔ جدول را نباید با پیکسلِ گوشهٔ ناحیه اشتباه گرفت؛ هرکدام خلاصهٔ یک پیشوند بزرگ‌ترند.

پس از ساخت جدول، بخش حسابیِ پرسش چهار مقدار از جدول می‌خواند و سه عمل جمع یا تفریق انجام می‌دهد؛ این تعداد به مساحت ناحیه وابسته نیست. بررسی نوع و حدودِ مختصات هم انجام می‌شود. «چهار خواندن» یعنی چهار خانهٔ جدول؛ تعداد همهٔ دسترسی‌های داخلیِ tuple، دستورهای مفسر یا انتقال‌های حافظه را با آن اندازه نگرفته‌ایم.

این نمونه با صحیح‌های پایتون و دامنهٔ محدود حساب می‌کند؛ تلورانس ممیز شناور لازم نیست. بیشترین جمعِ مجاز، شانزده ضرب‌در شانزده ضرب‌در ۲۵۵، یعنی ۶۵۲۸۰ است. اگر بعدها به آرایهٔ نوع‌دار یا دستگاه دیگری منتقل شود، نوعِ انباشت باید جدا بررسی شود؛ موفقیت این کد، ایمنیِ جمع در همهٔ انواع عددیِ کتابخانه‌ها را ثابت نمی‌کند.

۴. کد را با همهٔ مستطیل‌های تصویر کوچک بسنجیم

فایل integral_image_sums.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. تابع ساخت، شیء دارای ابعاد و جدولِ tuple برمی‌گرداند؛ تابع پرسش برای خروجیِ معتبرِ همان سازنده طراحی شده است. دست‌کاریِ عمدیِ درونِ یک شیء ساختگی اعتبارسنجی نمی‌شود. frozen جلوی انتساب معمول به فیلدها را می‌گیرد و تضمین امنیت یا اصالت شیء نیست.

"""Own bounded, exact summed-area table; no third-party library executed."""
from dataclasses import dataclass, FrozenInstanceError
import json
import platform


@dataclass(frozen=True)
class IntegralImage:
    height: int
    width: int
    table: tuple


def build_integral(image):
    if type(image) is not tuple or not 1 <= len(image) <= 16:
        raise ValueError("image must have 1..16 tuple rows")
    if type(image[0]) is not tuple or not 1 <= len(image[0]) <= 16:
        raise ValueError("rows must have 1..16 pixels")
    height, width = len(image), len(image[0])
    for row in image:
        if type(row) is not tuple or len(row) != width:
            raise ValueError("image must be rectangular with tuple rows")
        if any(type(v) is not int or not 0 <= v <= 255 for v in row):
            raise ValueError("pixel must be an actual integer in 0..255")
    table = [[0] * (width + 1) for _ in range(height + 1)]
    for r, row in enumerate(image):
        running = 0
        for c, value in enumerate(row):
            running += value
            table[r + 1][c + 1] = table[r][c + 1] + running
    return IntegralImage(height, width, tuple(tuple(row) for row in table))


def rectangle_sum(prefix, r0, r1, c0, c1):
    """Trusted build_integral output; row and column ends are excluded."""
    if type(prefix) is not IntegralImage:
        raise ValueError("use the object returned by build_integral")
    if any(type(v) is not int for v in (r0, r1, c0, c1)):
        raise ValueError("rectangle coordinates must be actual integers")
    if not (0 <= r0 <= r1 <= prefix.height and
            0 <= c0 <= c1 <= prefix.width):
        raise ValueError("ordered rectangle must lie within the image")
    table = prefix.table
    return table[r1][c1] - table[r0][c1] - table[r1][c0] + table[r0][c0]


def rejects(call):
    try:
        call()
    except ValueError:
        return True
    return False


def main():
    image = ((2, 1, 4, 0), (3, 5, 0, 2), (1, 0, 6, 1))
    prefix = build_integral(image)
    expected = ((0, 0, 0, 0, 0), (0, 2, 3, 7, 7),
                (0, 5, 11, 15, 17), (0, 6, 12, 22, 25))
    checks = {}
    checks["literal_zero_border_prefix_table"] = prefix.table == expected
    checks["hand_entire_image_sum"] = rectangle_sum(prefix, 0, 3, 0, 4) == 25
    checks["hand_interior_half_open_rectangle"] = rectangle_sum(prefix, 1, 3, 1, 4) == 14
    checks["single_pixel_queries_preserve_locations"] = all(
        rectangle_sum(prefix, r, r + 1, c, c + 1) == image[r][c]
        for r in range(3) for c in range(4))
    checks["all_zero_area_rectangles_return_zero"] = all(
        rectangle_sum(prefix, r0, r1, c0, c1) == 0
        for r0 in range(4) for r1 in range(r0, 4)
        for c0 in range(5) for c1 in range(c0, 5)
        if r0 == r1 or c0 == c1)
    # Independent oracle reads the literal image slices, never the table.
    oracle_cases = 0
    oracle_ok = True
    for r0 in range(3):
        for r1 in range(r0 + 1, 4):
            for c0 in range(4):
                for c1 in range(c0 + 1, 5):
                    direct = sum(sum(row[c0:c1]) for row in image[r0:r1])
                    oracle_ok = oracle_ok and rectangle_sum(prefix, r0, r1, c0, c1) == direct
                    oracle_cases += 1
    checks["all_60_nonempty_rectangles_match_independent_slices_one_group"] = (
        oracle_ok and oracle_cases == 60)
    checks["horizontal_and_vertical_partitions_add"] = (
        rectangle_sum(prefix, 0, 1, 0, 4) + rectangle_sum(prefix, 1, 3, 0, 4) == 25
        and rectangle_sum(prefix, 0, 3, 0, 2) + rectangle_sum(prefix, 0, 3, 2, 4) == 25)
    checks["singleton_one_row_one_column"] = (
        rectangle_sum(build_integral(((7,),)), 0, 1, 0, 1) == 7
        and rectangle_sum(build_integral(((1, 2, 3),)), 0, 1, 1, 3) == 5
        and rectangle_sum(build_integral(((1,), (2,), (3,))), 1, 3, 0, 1) == 5)
    checks["maximum_shape_value_and_exact_accumulation"] = (
        rectangle_sum(build_integral(tuple((255,) * 16 for _ in range(16))),
                      0, 16, 0, 16) == 65280)
    checks["zero_image_and_positive_scale"] = (
        rectangle_sum(build_integral(((0, 0), (0, 0))), 0, 2, 0, 2) == 0
        and rectangle_sum(build_integral(tuple(tuple(2 * v for v in row)
                                               for row in image)), 1, 3, 1, 4) == 28)
    checks["reject_wrong_image_and_row_types_or_shapes"] = all(
        rejects(lambda bad=bad: build_integral(bad))
        for bad in (None, [], (), ((1,), (1, 2)), ([],), ((),),
                    ((1,) * 17,), tuple((1,) for _ in range(17)), ((1,), [2])))
    checks["reject_bool_float_negative_or_out_of_range_pixels"] = all(
        rejects(lambda bad=bad: build_integral(((bad,),)))
        for bad in (True, False, 1.0, float("nan"), float("inf"), -1, 256, "2", 10**400))
    checks["reject_bool_float_and_other_query_coordinate_types"] = all(
        rejects(lambda bad=bad: rectangle_sum(prefix, bad, 3, 0, 4))
        for bad in (True, False, 0.0, None, "0"))
    checks["reject_reversed_or_outside_rectangles"] = all(
        rejects(lambda box=box: rectangle_sum(prefix, *box))
        for box in ((-1, 3, 0, 4), (0, 4, 0, 4), (2, 1, 0, 4),
                    (0, 3, -1, 4), (0, 3, 0, 5), (0, 3, 3, 2), (0, 10**400, 0, 4)))
    saved_table = prefix.table
    repeated = [rectangle_sum(prefix, 1, 3, 1, 4) for _ in range(3)]
    try:
        prefix.height = 99
        frozen = False
    except FrozenInstanceError:
        frozen = True
    checks["queries_do_not_modify_table_or_image_and_normal_assignment_is_frozen"] = (
        repeated == [14, 14, 14] and prefix.table == saved_table and
        image == ((2, 1, 4, 0), (3, 5, 0, 2), (1, 0, 6, 1)) and frozen)
    checks["query_requires_own_integral_object"] = rejects(
        lambda: rectangle_sum(expected, 1, 3, 1, 4))
    assert all(type(value) is bool and value for value in checks.values())
    print(json.dumps({
        "python": platform.python_version(),
        "dependencies": {"standard_library_only": True, "opencv_executed": False,
                         "scikit_image_executed": False},
        "image": image, "prefix": prefix.table,
        "whole_sum": rectangle_sum(prefix, 0, 3, 0, 4),
        "rectangle": {"rows_half_open": [1, 3], "columns_half_open": [1, 4], "sum": 14},
        "independent_oracle": {"nonempty_rectangle_cases": oracle_cases, "all_equal": oracle_ok},
        "theoretical_storage": {"image_values": 12, "prefix_values": 20,
                                "bytes_measured": False},
        "query_arithmetic_model": {"table_cell_reads": 4, "integer_add_subtract_operations": 3,
                                   "includes_validation_or_memory_cost": False},
        "checks": checks,
        "limitations": ["Trusted builder output, not validation of fabricated dataclass internals.",
                        "Static image: a changed pixel requires rebuilding the table.",
                        "No measured speed, memory bytes, image quality or library API parity."]
    }, ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()

شانزده گروهِ بررسیِ نام‌دار، مقدار بولیِ درست داده‌اند. مرجع مستقل روی خودِ تصویرِ اولیه برشِ سطرها و ستون‌ها می‌گیرد و مقادیر را مستقیم جمع می‌کند؛ جدول پیشوند یا فرمولِ چهارگوشه را به‌عنوان پاسخِ مورد انتظار صدا نمی‌زند. هر شصت مستطیلِ غیرخالیِ نمونه در یک گروه با این مرجع مقایسه می‌شوند؛ شصت حالت، شصت گروه تازه نیست.

جدولِ دستی، کل تصویر، تک‌پیکسل‌ها، ناحیه‌های خالی، تک‌سطر و تک‌ستون نیز بررسی شده‌اند. تقسیمِ تصویر به دو بخشِ بدون هم‌پوشانی باید جمعِ کل را حفظ کند؛ دو برابر کردنِ شدت‌های همین نمونه نیز جوابِ چهارده را بیست‌وهشت می‌کند. ورودی نامعتبر، مرز وارونه، تغییرنکردن داده و پرسش تکراری جدا پوشش داده شده‌اند. اجرای مجدد به شمار بررسی‌های یکتا اضافه نمی‌شود.

۵. هزینهٔ آماده‌سازی و حافظه را کنار پرس‌وجو ببینیم

ساخت جدول با یک گذر روی H×W خانه انجام می‌شود و فضای جدول با اندازهٔ تصویر رشد می‌کند. در نمونه، دوازده مقدارِ ورودی و بیست مقدارِ جدول داریم؛ این شمارِ خانه‌هاست، نه بایتِ حافظهٔ اندازه‌گیری‌شده. شیءهای صحیح، tupleها، فهرستِ میانی و هزینهٔ تخصیص در پایتون با تعداد خانه یکسان نیستند.

{
  "python": "3.14.5",
  "dependencies": {
    "standard_library_only": true,
    "opencv_executed": false,
    "scikit_image_executed": false
  },
  "image": [
    [
      2,
      1,
      4,
      0
    ],
    [
      3,
      5,
      0,
      2
    ],
    [
      1,
      0,
      6,
      1
    ]
  ],
  "prefix": [
    [
      0,
      0,
      0,
      0,
      0
    ],
    [
      0,
      2,
      3,
      7,
      7
    ],
    [
      0,
      5,
      11,
      15,
      17
    ],
    [
      0,
      6,
      12,
      22,
      25
    ]
  ],
  "whole_sum": 25,
  "rectangle": {
    "rows_half_open": [
      1,
      3
    ],
    "columns_half_open": [
      1,
      4
    ],
    "sum": 14
  },
  "independent_oracle": {
    "nonempty_rectangle_cases": 60,
    "all_equal": true
  },
  "theoretical_storage": {
    "image_values": 12,
    "prefix_values": 20,
    "bytes_measured": false
  },
  "query_arithmetic_model": {
    "table_cell_reads": 4,
    "integer_add_subtract_operations": 3,
    "includes_validation_or_memory_cost": false
  },
  "checks": {
    "literal_zero_border_prefix_table": true,
    "hand_entire_image_sum": true,
    "hand_interior_half_open_rectangle": true,
    "single_pixel_queries_preserve_locations": true,
    "all_zero_area_rectangles_return_zero": true,
    "all_60_nonempty_rectangles_match_independent_slices_one_group": true,
    "horizontal_and_vertical_partitions_add": true,
    "singleton_one_row_one_column": true,
    "maximum_shape_value_and_exact_accumulation": true,
    "zero_image_and_positive_scale": true,
    "reject_wrong_image_and_row_types_or_shapes": true,
    "reject_bool_float_negative_or_out_of_range_pixels": true,
    "reject_bool_float_and_other_query_coordinate_types": true,
    "reject_reversed_or_outside_rectangles": true,
    "queries_do_not_modify_table_or_image_and_normal_assignment_is_frozen": true,
    "query_requires_own_integral_object": true
  },
  "limitations": [
    "Trusted builder output, not validation of fabricated dataclass internals.",
    "Static image: a changed pixel requires rebuilding the table.",
    "No measured speed, memory bytes, image quality or library API parity."
  ]
}

برای پرسشی کوچک یا یک‌بارمصرف، هزینهٔ آماده‌سازی ممکن است ارزش نداشته باشد؛ مزیت الگوریتمی برای پرسش‌های مستطیلیِ تکرارشونده روی تصویرِ ثابت مطرح است. با تغییر یک پیکسل، این جدولِ قبلی دیگر خلاصهٔ تصویر تازه نیست و در این پیاده‌سازی باید بازسازی شود. زمان‌سنجی، نقطهٔ سربه‌سر، مصرف حافظهٔ واقعی یا شتاب محصول گزارش نشده است.

هموارسازی جدایی‌پذیر تصویر میانگین وزن‌دارِ همسایگی با مرز مشخص را محاسبه می‌کند و آستانه‌گذاری Otsu از توزیع شدت، تقسیم دودویی می‌سازد. این جدول هیچ‌کدام نیست؛ فقط جمعِ ناحیه را پاسخ می‌دهد. منابع در ۲۵ مهر ۱۴۰۵ خوانده شدند؛ تاریخ اصلی انتشارِ این صفحات مشخص نیست و آموزش را خبر تازه معرفی نمی‌کنیم.

پرسش اول: چرا جدول یک سطر و ستون بیشتر دارد؟ پاسخ: برای نمایشِ جمعِ پیشوندِ خالی؛ حاشیه صفر است و پرسشِ چسبیده به بالا یا چپ نیز همان فرمولِ چهارگوشه را دارد.

پرسش دوم: جمعِ سطرهای یک تا پیش از سه و ستون‌های یک تا پیش از چهار چیست؟ پاسخ: چهارده؛ شش پیکسل انتخاب می‌شوند و چهار مقدار جدول بیست‌وپنج، هفت، شش و دو هستند.

پرسش سوم: آیا ناحیهٔ خالی میانگین صفر دارد؟ پاسخ: خیر؛ فقط جمع را صفر قرارداد کرده‌ایم. میانگین به تقسیم بر تعداد خانه نیاز دارد و تعدادِ صفر اجازهٔ آن تقسیم را نمی‌دهد.

پرسش چهارم: آیا چهار خواندن، شتابِ قطعی را ثابت می‌کند؟ پاسخ: خیر؛ ساخت و حافظه هزینه دارند و زمان واقعی سنجیده نشده است. همچنین تصویرِ تغییرکرده به جدول تازه نیاز دارد؛ جدولِ کهنه پاسخِ معتبرِ دادهٔ جدید نیست.

منابع و مطالعهٔ بیشتر

• OpenCV 4.13؛ جدول پیشوند با حاشیهٔ صفر و جمع چهارگوشه
• scikit-image 0.26؛ جدول شامل و انتهای شاملِ integrate

بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.