فاصلهٔ شهریِ ماسک تصویر در پایتون؛ دو گذر و قراردادِ پس‌زمینه

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

۱. فاصله تا کدام پیکسل و با چه واحدی؟

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

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

مرجعِ distance_transform_cdt در SciPy فاصلهٔ پیش‌زمینه تا صفر و انتخابِ taxicab را توضیح می‌دهد؛ پیش‌فرضِ آن chessboard است. یک نامِ عمومیِ «تبدیلِ فاصله» برای مقایسه کافی نیست. حتی با شکلِ یکسانِ دو خروجی، عوض‌شدنِ متریک یا معنای صفر می‌تواند مسئلهٔ دیگری بسازد. ما پارامترِ انتخابی نداریم و همین قراردادِ شهریِ ثابت را پیاده می‌کنیم.

۲. گذرِ رفت و برگشت روی شبکهٔ محدود

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

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

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

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

۳. ماسکِ کوچک و تفاوتِ قطر با گامِ محوری

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

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

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

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

۴. کدِ کامل و مرجعِ همهٔ پیکسل‌های صفر

کدِ کامل با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. فایلِ cityblock_distance_contract.py را ذخیره کنید و با پایتون اجرا کنید؛ خروجی، JSON و بررسی‌های نام‌دار است. SciPy و MATLAB اجرا نشده‌اند. مرجعِ distance_transform_bf در SciPy رویکردِ جست‌وجوی کامل و متریک‌هایش را توضیح می‌دهد؛ پیش‌فرضِ آن اقلیدسی است، پس حذفِ نامِ متریک حتی در مرجعِ مقایسه بی‌اثر نیست.

"""Finite synthetic cityblock distance to in-image zero pixels, not clearance."""
from itertools import product
import json
import platform


def cityblock_distance(mask):
    """Exact tuple grid1..12, exact int bits, at least one background zero.

    Return two fresh tuple matrices: partial forward scan and final distance.
    No out-of-image reference, obstacle costs, spacing or nearest-pixel index.
    """
    if type(mask) is not tuple or not 1 <= len(mask) <= 12:
        raise ValueError("grid_shape")
    if type(mask[0]) is not tuple or not 1 <= len(mask[0]) <= 12:
        raise ValueError("grid_shape")
    height, width = len(mask), len(mask[0])
    if any(type(row) is not tuple or len(row) != width for row in mask):
        raise ValueError("grid_shape")
    if any(type(value) is not int or value not in (0, 1)
           for row in mask for value in row):
        raise ValueError("binary_pixel")
    if not any(value == 0 for row in mask for value in row):
        raise ValueError("no_in_image_background")
    sentinel = height + width  # Strictly above maximum finite distance h+w-2.
    distance = [[0 if value == 0 else sentinel for value in row] for row in mask]
    for r in range(height):
        for c in range(width):
            if r > 0:
                distance[r][c] = min(distance[r][c], distance[r - 1][c] + 1)
            if c > 0:
                distance[r][c] = min(distance[r][c], distance[r][c - 1] + 1)
    forward = tuple(tuple(row) for row in distance)
    for r in range(height - 1, -1, -1):
        for c in range(width - 1, -1, -1):
            if r + 1 < height:
                distance[r][c] = min(distance[r][c], distance[r + 1][c] + 1)
            if c + 1 < width:
                distance[r][c] = min(distance[r][c], distance[r][c + 1] + 1)
    return {"after_forward": forward,
            "distance": tuple(tuple(row) for row in distance)}


def all_background_oracle(mask):
    """Valid-fixture reference: direct coordinates, no scans or main calls."""
    zeros = [(r, c) for r, row in enumerate(mask)
             for c, value in enumerate(row) if value == 0]
    return tuple(tuple(min(abs(r - zr) + abs(c - zc) for zr, zc in zeros)
                       for c in range(len(mask[0]))) for r in range(len(mask)))


def transpose(matrix):
    return tuple(tuple(row[c] for row in matrix) for c in range(len(matrix[0])))


def rejects(value, category):
    try:
        cityblock_distance(value)
    except ValueError as error:
        return str(error) == category
    return False


def run():
    mask = ((0, 1, 1, 1, 1), (1, 1, 1, 1, 1), (1, 1, 1, 1, 0))
    snapshot = tuple(tuple(row) for row in mask)
    result = cityblock_distance(mask)
    expected = ((0, 1, 2, 3, 2), (1, 2, 3, 2, 1), (2, 3, 2, 1, 0))
    corner = ((1, 1, 1), (1, 1, 1), (1, 1, 0))
    reverse_needed = cityblock_distance(corner)
    checks = {}
    checks["hand_three_by_five_distance_and_shape"] = result["distance"] == expected
    checks["zero_pixels_and_single_background_have_zero_distance"] = (
        cityblock_distance(((0,),))["distance"] == ((0,),)
        and cityblock_distance(((0, 0), (0, 0)))["distance"] == ((0, 0), (0, 0))
    )
    checks["backward_scan_is_essential_for_bottom_right_reference"] = (
        reverse_needed["after_forward"][0][0] == 6
        and reverse_needed["distance"] == ((4, 3, 2), (3, 2, 1), (2, 1, 0))
    )
    diagonal = ((0, 1), (1, 1))
    checks["diagonal_requires_two_axial_steps_not_one_or_sqrt_two"] = (
        cityblock_distance(diagonal)["distance"] == ((0, 1), (1, 2))
    )
    checks["finite_image_has_no_outside_zero_or_edge_wrap"] = (
        cityblock_distance(((1, 1, 1, 1, 0),))["distance"] == ((4, 3, 2, 1, 0),)
        and cityblock_distance(((1,), (1,), (0,)))["distance"] == ((2,), (1,), (0,))
    )
    checks["all_foreground_rejected_instead_of_silently_padding"] = all(
        rejects(full, "no_in_image_background")
        for full in (((1,),), ((1, 1), (1, 1)), ((1,) * 12,) * 12)
    )
    class TupleSubclass(tuple):
        pass
    invalid_shapes = [None, [], (), ((),), ((0,), (1, 0)), ([0],),
                      TupleSubclass(((0,),)), (TupleSubclass((0,)),),
                      ((0,) * 13,), ((0,),) * 13]
    checks["strict_container_rectangular_shape_and_upper_bounds"] = all(
        rejects(value, "grid_shape") for value in invalid_shapes
    )
    class IntSubclass(int):
        pass
    checks["strict_pixel_bits_exclude_bool_subclasses_and_coercion"] = all(
        rejects(((0, value),), "binary_pixel")
        for value in (True, False, 1.0, "1", None, -1, 2, IntSubclass(1))
    )
    oracle_count = 0
    oracle_ok = symmetry_ok = local_ok = adding_background_ok = True
    additions = 0
    for bits in product((0, 1), repeat=9):
        if 0 not in bits:
            continue
        small = tuple(tuple(bits[3 * r + c] for c in range(3)) for r in range(3))
        dist = cityblock_distance(small)["distance"]
        oracle_ok &= dist == all_background_oracle(small)
        oracle_count += 1
        symmetry_ok &= cityblock_distance(transpose(small))["distance"] == transpose(dist)
        symmetry_ok &= cityblock_distance(tuple(row[::-1] for row in small))["distance"] == tuple(row[::-1] for row in dist)
        for r in range(3):
            for c in range(3):
                local_ok &= (dist[r][c] == 0) == (small[r][c] == 0)
                local_ok &= type(dist[r][c]) is int and 0 <= dist[r][c] <= 4
                if r + 1 < 3:
                    local_ok &= abs(dist[r][c] - dist[r + 1][c]) <= 1
                if c + 1 < 3:
                    local_ok &= abs(dist[r][c] - dist[r][c + 1]) <= 1
                if small[r][c] == 1:
                    changed = tuple(tuple(0 if (rr, cc) == (r, c) else small[rr][cc]
                                          for cc in range(3)) for rr in range(3))
                    after = cityblock_distance(changed)["distance"]
                    adding_background_ok &= all(after[rr][cc] <= dist[rr][cc]
                                                for rr in range(3) for cc in range(3))
                    additions += 1
    checks["all_511_small_masks_match_independent_all_zero_coordinate_oracle"] = (
        oracle_count == 511 and bool(oracle_ok)
    )
    checks["paired_transpose_and_reflection_preserve_distance_geometry"] = bool(symmetry_ok)
    checks["all_small_fields_preserve_zero_set_bounds_and_neighbor_lipschitz"] = bool(local_ok)
    checks["adding_background_never_increases_any_small_fixture_distance"] = (
        additions == 2295 and bool(adding_background_ok)
    )
    boundary_ok = True
    for zr in range(12):
        for zc in range(12):
            large = tuple(tuple(int((r, c) != (zr, zc)) for c in range(12))
                          for r in range(12))
            boundary_ok &= cityblock_distance(large)["distance"] == all_background_oracle(large)
    checks["all_144_single_background_12_by_12_positions_match_oracle"] = bool(boundary_ok)
    exposed = cityblock_distance(mask)
    exposed["distance"] = ((99,),)
    checks["input_and_fresh_result_container_are_independent"] = (
        mask == snapshot and cityblock_distance(mask) == result
    )
    if not all(type(value) is bool and value for value in checks.values()):
        raise AssertionError(checks)
    return {
        "python": platform.python_version(), "dependencies": "standard library only",
        "case_kind": "synthetic exact finite binary-grid geometry, not image quality or clearance",
        "input_mask": mask, "background_coordinates_rc": [[0, 0], [2, 4]],
        "distance_unit": "one unweighted axial pixel step", "outside_image": "not a reference",
        "after_forward_partial": result["after_forward"], "distance": result["distance"],
        "max_distance": max(value for row in result["distance"] for value in row),
        "bottom_right_zero_forward_corner_sentinel": reverse_needed["after_forward"][0][0],
        "bottom_right_zero_final_corner_distance": reverse_needed["distance"][0][0],
        "oracle_cases_inside_groups": {"all_nonempty_background_3_by_3_masks": oracle_count,
                                       "one_zero_12_by_12_positions": 144,
                                       "single_foreground_to_zero_additions": additions},
        "checks": checks, "check_count": len(checks), "all_passed": True,
        "limitations": ["Exact tuple rows and int0or1 only; each dimension1..12; bool excluded",
                        "At least one in-image zero required; no external padding or periodic boundary",
                        "No nearest-reference tie/index, obstacle path, Euclidean or calibrated physical distance",
                        "No SciPy/MATLAB execution, API-byte parity, version rollback, camera, hardware or timing claim"],
    }


if __name__ == "__main__":
    print(json.dumps(run(), ensure_ascii=False, indent=2, allow_nan=False))

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

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

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

۵. چهار پرسش پیش از مقایسهٔ نسخه‌ها

{
  "python": "3.14.5",
  "dependencies": "standard library only",
  "case_kind": "synthetic exact finite binary-grid geometry, not image quality or clearance",
  "input_mask": [
    [
      0,
      1,
      1,
      1,
      1
    ],
    [
      1,
      1,
      1,
      1,
      1
    ],
    [
      1,
      1,
      1,
      1,
      0
    ]
  ],
  "background_coordinates_rc": [
    [
      0,
      0
    ],
    [
      2,
      4
    ]
  ],
  "distance_unit": "one unweighted axial pixel step",
  "outside_image": "not a reference",
  "after_forward_partial": [
    [
      0,
      1,
      2,
      3,
      4
    ],
    [
      1,
      2,
      3,
      4,
      5
    ],
    [
      2,
      3,
      4,
      5,
      0
    ]
  ],
  "distance": [
    [
      0,
      1,
      2,
      3,
      2
    ],
    [
      1,
      2,
      3,
      2,
      1
    ],
    [
      2,
      3,
      2,
      1,
      0
    ]
  ],
  "max_distance": 3,
  "bottom_right_zero_forward_corner_sentinel": 6,
  "bottom_right_zero_final_corner_distance": 4,
  "oracle_cases_inside_groups": {
    "all_nonempty_background_3_by_3_masks": 511,
    "one_zero_12_by_12_positions": 144,
    "single_foreground_to_zero_additions": 2295
  },
  "checks": {
    "hand_three_by_five_distance_and_shape": true,
    "zero_pixels_and_single_background_have_zero_distance": true,
    "backward_scan_is_essential_for_bottom_right_reference": true,
    "diagonal_requires_two_axial_steps_not_one_or_sqrt_two": true,
    "finite_image_has_no_outside_zero_or_edge_wrap": true,
    "all_foreground_rejected_instead_of_silently_padding": true,
    "strict_container_rectangular_shape_and_upper_bounds": true,
    "strict_pixel_bits_exclude_bool_subclasses_and_coercion": true,
    "all_511_small_masks_match_independent_all_zero_coordinate_oracle": true,
    "paired_transpose_and_reflection_preserve_distance_geometry": true,
    "all_small_fields_preserve_zero_set_bounds_and_neighbor_lipschitz": true,
    "adding_background_never_increases_any_small_fixture_distance": true,
    "all_144_single_background_12_by_12_positions_match_oracle": true,
    "input_and_fresh_result_container_are_independent": true
  },
  "check_count": 14,
  "all_passed": true,
  "limitations": [
    "Exact tuple rows and int0or1 only; each dimension1..12; bool excluded",
    "At least one in-image zero required; no external padding or periodic boundary",
    "No nearest-reference tie/index, obstacle path, Euclidean or calibrated physical distance",
    "No SciPy/MATLAB execution, API-byte parity, version rollback, camera, hardware or timing claim"
  ]
}

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

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

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

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

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

• SciPy؛ تعریفِ تبدیلِ فاصله و انتخابِ صریحِ taxicab در distance_transform_cdt
• SciPy؛ مرجعِ جست‌وجوی کاملِ distance_transform_bf و تفاوتِ پیش‌فرضِ متریک

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