ناحیه‌های متصل ماسک تصویر در پایتون؛ همسایگی چهار و هشت و باکس نیمه‌باز

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

۱. ورودی ماسک و معنای برچسب‌ها را ثابت کنیم

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

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

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

۲. همسایگی لبه‌ای و قطری پاسخ متفاوت می‌دهند

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

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

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

۳. مساحت ناحیه با مستطیل پیرامون آن برابر نیست

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

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

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

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

۴. کد کامل را با دو روش مستقل بررسی کنیم

فایل connected_components.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. مسیر اصلی برای هر پیکسل آغازین، جست‌وجوی سطح‌اول یا BFS انجام می‌دهد. صف deque پیکسل‌های در انتظار را نگه می‌دارد. پیکسل هنگام ورود به صف برچسب می‌گیرد؛ در نتیجه از چند همسایه دوباره وارد همان صف نمی‌شود.

"""Original bounded binary-mask components; no camera or defect inference."""
from collections import deque
from itertools import product
import json
import platform


def label_components(mask, connectivity=4):
    if type(connectivity) is not int or connectivity not in (4, 8):
        raise ValueError('connectivity')
    if type(mask) is not list or not 1 <= len(mask) <= 32:
        raise ValueError('mask_shape')
    if type(mask[0]) is not list or not 1 <= len(mask[0]) <= 32:
        raise ValueError('mask_shape')
    height, width = len(mask), len(mask[0])
    for row in mask:
        if type(row) is not list or len(row) != width:
            raise ValueError('mask_shape')
        if any(type(value) is not int or value not in (0, 1) for value in row):
            raise ValueError('binary_pixel')
    labels = [[0] * width for _ in range(height)]
    offsets = [(-1, 0), (0, -1), (0, 1), (1, 0)]
    if connectivity == 8:
        offsets += [(-1, -1), (-1, 1), (1, -1), (1, 1)]
    components = []
    for row in range(height):
        for col in range(width):
            if mask[row][col] == 0 or labels[row][col] != 0:
                continue
            label = len(components) + 1
            queue = deque([(row, col)])
            labels[row][col] = label
            points = []
            while queue:
                r, c = queue.popleft()
                points.append((r, c))
                for dr, dc in offsets:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < height and 0 <= nc < width and mask[nr][nc] == 1 and labels[nr][nc] == 0:
                        labels[nr][nc] = label
                        queue.append((nr, nc))
            rows, cols = [p[0] for p in points], [p[1] for p in points]
            components.append({'label': label, 'area_pixels': len(points),
                               'bbox_rc_half_open': [min(rows), min(cols), max(rows) + 1, max(cols) + 1]})
    return {'connectivity': connectivity, 'shape': [height, width],
            'component_count': len(components), 'labels': labels, 'components': components}


def pairwise_union_find_oracle(mask, connectivity):
    """Independent all-pairs adjacency + Union-Find; no BFS/offset list."""
    points = [(r, c) for r, row in enumerate(mask) for c, value in enumerate(row) if value == 1]
    parent = list(range(len(points)))
    def find(index):
        while parent[index] != index:
            index = parent[index]
        return index
    for i, (r1, c1) in enumerate(points):
        for j in range(i):
            r2, c2 = points[j]
            distance = abs(r1 - r2) + abs(c1 - c2) if connectivity == 4 else max(abs(r1 - r2), abs(c1 - c2))
            if distance == 1:
                parent[find(i)] = find(j)
    groups = {}
    for i, point in enumerate(points):
        groups.setdefault(find(i), []).append(point)
    ordered = sorted(groups.values(), key=lambda group: min(group))
    output = [[0 for _ in row] for row in mask]
    records = []
    for number, group in enumerate(ordered, 1):
        for row, col in group:
            output[row][col] = number
        records.append({'label': number, 'area_pixels': len(group),
                        'bbox_rc_half_open': [min(r for r, c in group), min(c for r, c in group),
                                              1 + max(r for r, c in group), 1 + max(c for r, c in group)]})
    return {'connectivity': connectivity, 'shape': [len(mask), len(mask[0])],
            'component_count': len(ordered), 'labels': output, 'components': records}


def rejects(call, message):
    try:
        call()
    except ValueError as error:
        return str(error) == message
    return False


def run_example():
    mask = [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 0], [1, 0, 0, 1]]
    untouched = [row[:] for row in mask]
    four, eight = label_components(mask, 4), label_components(mask, 8)
    single = label_components([[1]])
    zeros = label_components([[0, 0], [0, 0]], 8)
    ones = label_components([[1] * 3 for _ in range(2)])
    ring = label_components([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
    exposed = label_components(mask, 4)
    exposed['labels'][0][0] = 99
    exposed['components'][0]['bbox_rc_half_open'][0] = 99
    invalid_shapes = [None, [], [[]], [[0], [1, 0]], [0, 1], [(0, 1)]]
    invalid_pixels = [True, False, 1.0, '1', -1, 2, None]
    cases, oracle_ok, refinement_ok = 0, True, True
    for bits in product((0, 1), repeat=9):
        grid = [list(bits[i:i + 3]) for i in range(0, 9, 3)]
        outputs = [label_components(grid, conn) for conn in (4, 8)]
        for result in outputs:
            oracle_ok &= result == pairwise_union_find_oracle(grid, result['connectivity'])
            cases += 1
        refinement_ok &= outputs[1]['component_count'] <= outputs[0]['component_count']
        for component in outputs[0]['components']:
            destinations = {outputs[1]['labels'][r][c] for r in range(3) for c in range(3)
                            if outputs[0]['labels'][r][c] == component['label']}
            refinement_ok &= len(destinations) == 1
    checks = {
        'hand_four_connected_labels': four['labels'] == [[1, 0, 0, 2], [0, 3, 0, 2], [0, 0, 4, 0], [5, 0, 0, 6]],
        'hand_four_connected_count_and_areas': four['component_count'] == 6 and [c['area_pixels'] for c in four['components']] == [1, 2, 1, 1, 1, 1],
        'hand_eight_connected_labels_and_areas': eight['labels'] == [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 0], [2, 0, 0, 1]] and [c['area_pixels'] for c in eight['components']] == [6, 1],
        'hand_half_open_bounding_boxes': four['components'][1]['bbox_rc_half_open'] == [0, 3, 2, 4] and eight['components'][0]['bbox_rc_half_open'] == [0, 0, 4, 4],
        'single_pixel_has_unit_area_and_box': single['components'] == [{'label': 1, 'area_pixels': 1, 'bbox_rc_half_open': [0, 0, 1, 1]}],
        'all_zero_mask_has_no_components': zeros['component_count'] == 0 and zeros['components'] == [] and zeros['labels'] == [[0, 0], [0, 0]],
        'all_one_mask_is_one_region': ones['component_count'] == 1 and ones['components'][0]['area_pixels'] == 6 and ones['components'][0]['bbox_rc_half_open'] == [0, 0, 2, 3],
        'diagonal_pair_depends_on_connectivity': label_components([[1, 0], [0, 1]], 4)['component_count'] == 2 and label_components([[1, 0], [0, 1]], 8)['component_count'] == 1,
        'opposite_edges_do_not_wrap': all(label_components([[1, 0, 1]], conn)['component_count'] == 2 for conn in (4, 8)),
        'hole_is_not_filled_or_counted_as_area': ring['component_count'] == 1 and ring['components'][0]['area_pixels'] == 8 and ring['labels'][1][1] == 0 and ring['components'][0]['bbox_rc_half_open'] == [0, 0, 3, 3],
        'foreground_mass_and_background_preserved': all(sum(c['area_pixels'] for c in result['components']) == 7 and all((result['labels'][r][c] == 0) == (mask[r][c] == 0) for r in range(4) for c in range(4)) for result in [four, eight]),
        'invalid_empty_or_ragged_masks_reject': all(rejects(lambda value=value: label_components(value), 'mask_shape') for value in invalid_shapes),
        'strict_binary_pixel_type_and_value': all(rejects(lambda value=value: label_components([[0, value]]), 'binary_pixel') for value in invalid_pixels),
        'connectivity_bool_and_unknown_reject': all(rejects(lambda value=value: label_components([[1]], value), 'connectivity') for value in [True, 1, 6, 4.0, '8']),
        'bounded_dimensions_include_32_reject_33': label_components([[1] * 32 for _ in range(32)])['components'][0]['area_pixels'] == 1024 and rejects(lambda: label_components([[1] * 33]), 'mask_shape') and rejects(lambda: label_components([[1]] * 33), 'mask_shape'),
        'all_four_regions_refine_eight_regions': bool(refinement_ok),
        'independent_pairwise_union_find_oracle': cases == 1024 and bool(oracle_ok),
        'inputs_and_fresh_outputs_remain_independent': mask == untouched and label_components(mask, 4) == four,
    }
    assert len(checks) == 18 and all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
            'scope': 'Bounded synthetic binary masks only; component is pixel adjacency, not physical object/defect or medical finding',
            'results': {'input_mask': mask, 'four_connected': four, 'eight_connected': eight,
                        'foreground_pixels': 7, 'oracle_scenarios_inside_one_group': cases,
                        'limits': {'max_rows': 32, 'max_columns': 32, 'binary_pixel': 'exact int0or1; bool excluded',
                                   'box_order': 'min_row,min_col,max_row_exclusive,max_col_exclusive',
                                   'canonical_label_order': 'row-major first encountered foreground'}},
            'checks': checks}


if __name__ == '__main__':
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

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

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

۵. مرز تصویر و چهار پرسش پاسخ‌دار را گزارش کنیم

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

{
  "python": "3.14.5",
  "dependencies": "Python standard library only",
  "scope": "Bounded synthetic binary masks only; component is pixel adjacency, not physical object/defect or medical finding",
  "results": {
    "input_mask": [
      [
        1,
        0,
        0,
        1
      ],
      [
        0,
        1,
        0,
        1
      ],
      [
        0,
        0,
        1,
        0
      ],
      [
        1,
        0,
        0,
        1
      ]
    ],
    "four_connected": {
      "connectivity": 4,
      "shape": [
        4,
        4
      ],
      "component_count": 6,
      "labels": [
        [
          1,
          0,
          0,
          2
        ],
        [
          0,
          3,
          0,
          2
        ],
        [
          0,
          0,
          4,
          0
        ],
        [
          5,
          0,
          0,
          6
        ]
      ],
      "components": [
        {
          "label": 1,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            0,
            0,
            1,
            1
          ]
        },
        {
          "label": 2,
          "area_pixels": 2,
          "bbox_rc_half_open": [
            0,
            3,
            2,
            4
          ]
        },
        {
          "label": 3,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            1,
            1,
            2,
            2
          ]
        },
        {
          "label": 4,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            2,
            2,
            3,
            3
          ]
        },
        {
          "label": 5,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            3,
            0,
            4,
            1
          ]
        },
        {
          "label": 6,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            3,
            3,
            4,
            4
          ]
        }
      ]
    },
    "eight_connected": {
      "connectivity": 8,
      "shape": [
        4,
        4
      ],
      "component_count": 2,
      "labels": [
        [
          1,
          0,
          0,
          1
        ],
        [
          0,
          1,
          0,
          1
        ],
        [
          0,
          0,
          1,
          0
        ],
        [
          2,
          0,
          0,
          1
        ]
      ],
      "components": [
        {
          "label": 1,
          "area_pixels": 6,
          "bbox_rc_half_open": [
            0,
            0,
            4,
            4
          ]
        },
        {
          "label": 2,
          "area_pixels": 1,
          "bbox_rc_half_open": [
            3,
            0,
            4,
            1
          ]
        }
      ]
    },
    "foreground_pixels": 7,
    "oracle_scenarios_inside_one_group": 1024,
    "limits": {
      "max_rows": 32,
      "max_columns": 32,
      "binary_pixel": "exact int0or1; bool excluded",
      "box_order": "min_row,min_col,max_row_exclusive,max_col_exclusive",
      "canonical_label_order": "row-major first encountered foreground"
    }
  },
  "checks": {
    "hand_four_connected_labels": true,
    "hand_four_connected_count_and_areas": true,
    "hand_eight_connected_labels_and_areas": true,
    "hand_half_open_bounding_boxes": true,
    "single_pixel_has_unit_area_and_box": true,
    "all_zero_mask_has_no_components": true,
    "all_one_mask_is_one_region": true,
    "diagonal_pair_depends_on_connectivity": true,
    "opposite_edges_do_not_wrap": true,
    "hole_is_not_filled_or_counted_as_area": true,
    "foreground_mass_and_background_preserved": true,
    "invalid_empty_or_ragged_masks_reject": true,
    "strict_binary_pixel_type_and_value": true,
    "connectivity_bool_and_unknown_reject": true,
    "bounded_dimensions_include_32_reject_33": true,
    "all_four_regions_refine_eight_regions": true,
    "independent_pairwise_union_find_oracle": true,
    "inputs_and_fresh_outputs_remain_independent": true
  }
}

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

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

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

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

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

• SciPy؛ label و همسایگی متقارن برای ناحیه‌های متصل
• scikit-image؛ label، همسایگی و پس‌زمینهٔ برچسب صفر
• scikit-image؛ regionprops و قرارداد باکس نیمه‌باز

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