Nội dung bài viết
Kim Uyên Toán Tử Khung Xương rút trích thành phần chính đại diện cho hình dạng của đối tượng trong ảnh nhị phân. Được ứng dụng trong nhận dạng mẫu (nhận dạng kí tự), nén ảnh (được giải mã bằng toán tử tái cấu trúc - reconstruction), phát hiện lỗi trên sản phẩm công nghiệp (đứt đoạn). Bài viết trình bày giải thuật thực hiện toán tử khung xương dựa trên các toán tử cơ bản hình thái học trên ảnh nhị phân.

Giới thiệu

Toán tử hình thái học được ứng dụng nhiều trong các lĩnh vực liên quan đến xử lý hình ảnh như: xử lý ảnh y khoa, nhận dạng mẫu (nhận dạng kí tự), phát hiện lỗi trên sản phẩm công nghiệp (lỗ hổng, đứt khúc, nứt). Có 2 vấn đề khiến toán tử hình thái học được sử dụng nhiều so với các toán tử dựa trên kỹ thuật convolution, trong các lĩnh vực kể trên, là do:

  • Tập trung vào xử lý hình dáng, cấu trúc đối tượng.
  • Dựa trên lý thuyết tập hợp, nên là toán tử phi tuyến, vì vậy, thời gian xử lý nhanh hơn phép tích chập (dựa trên cấu trúc đại số).

Toán tử khung xương được xây dựng từ các toán tử cơ bản trong phép toán hình thái học trên ảnh nhị phân. Bao gồm toán tử co (erosion), giãn (dilation), đóng (closing), mở (opening). Nhiều toán tử khác nhau cũng được xây dựng từ các toán tử cơ bản này: trích biên (boundary extraction), lấp vùng - lỗ hổng (filling region), làm mảnh (thinning), làm dày (thickness), tái cấu trúc (reconstruction), ...

Trong bài viết này, tôi trình bày giải thuật thực hiện toán tử khung xương (skeleton) dựa trên các toán tử cơ bản của toán tử hình thái học trên ảnh nhị phân.

ss_1_opencv    ss_2_skel_opencv

Trái: ảnh gốc.

Phải: ảnh sau khi xử lý để lấy khung xương.

Tiền đề bài viết

Bài viết bắt nguồn từ yêu cầu của một bạn quan tâm đến STDIO, muốn tìm hiểu toán tử này cho bài tập ở trường.

Đối tượng hướng đến

Bài viết dành cho các bạn đang học xử lý ảnh, có kiến thức lập trình C/C++, và thư viện openCV.

Toán tử cơ bản

Trước khi đi vào tìm hiểu toán tử khung xương, các bạn cần nắm được nội dung của các toán tử cơ bản của binary morphology. Bao gồm: co (erosion), giãn (dilation), đóng (closing), mở (opening).

Cũng như convolution, ma trận kernel quyết định kết quả của phép toán, thì đối với binary morphology, phần tử cấu trúc là thành phần quyết định hình dáng, cấu trúc của đối tượng.

Kí hiệu:

  • SE: phần tử cấu trúc.
  • A: tập các điểm thuộc đối tượng trong ảnh nhị phân (giá trị bằng 1).

Phần tử cấu trúc

SE là phần tử cấu trúc được biễu diễn trong không gian hai chiều, với anchor point của SE có tọa độ (0, 0). Ta định nghĩa các điểm p(x, y) = 1 thuộc SE.

Thư viện openCV hỗ trợ tạo phần tử cấu trúc sử dụng function:

Mat getStructuringElement (int shape, Size ksize, Point anchor=Point(-1,-1));

Trong đó:

  • shape có thể nhận một trong các giá trị sau: CV_SHAPE_RECT, CV_SHAPE_ELLIPSE, CV_SHAPE_CROSS.
  • ksize: kích thước phần tử cấu trúc.
  • anchor: điểm gốc với chỉ số dòng, chỉ số cột của SE. Nếu mặc định, thì điểm gốc có toạ độ: (ksize.x / 2, ksize.y / 2).

Trả về ma trận kích thước ksize, gồm 2 giá trị là: 1 (thuộc SE), 0 (không thuộc SE).

Nói rõ hơn về anchor point, xét về tính cục bộ, anchor point sẽ nhận tọa độ là chỉ số dòng, cột của ma trận trả về từ hàm. Xét trong không gian hai chiều, anchor point của SE đặt ở gốc tọa độ.

Ví dụ: ksize = (4, 4), anchor =  default-(2, 2).

ss_3_SE_4x4

Tùy vào kích thước đối tượng và toán tử áp dụng, mà bạn cần lựa chọn kích thước và hình dạng SE phù hợp. Xem ví dụ dưới đây, tôi đang muốn xóa nhiễu ảnh vân tay (trái cùng) sử dụng toán tử erosion, tôi chọn kích thước phần tử cấu trúc lần lượt là (3, 3) - kết quả trái và (5, 5) - kết quả phải:
ss_4_noisy_fingerprint   ss_5_noisy_fingerprint_erosed_3x3   ss_6_noisy_fingerprint_erosed_5x5

Binary Erosion

Toán tử có tác dụng làm mảnh đối tượng, xóa bỏ nhiễu và chi tiết thừa.

Minh họa

Trái: ảnh gốc. Phải: ảnh kết quả với ksize (3, 3); anchor point = default; shape = RECT

ss_4_noisy_fingerprint   ss_5_noisy_fingerprint_erosed_3x3

Định nghĩa

ss_7_Eqn_Erosion

Giải thích: Tịnh tiến SE theo vector w bất kỳ, và tại đó SE là tập con của A, thì giữ lại w đưa vào kết quả.

Theo suy nghĩ lập trình: duyệt qua tất cả các điểm trong A, tại mỗi điểm, đặt anchor point của SE tại điểm đang xét, kiểm tra nếu tất cả các điểm trong SE (giá trị bằng 1) và các điểm tương ứng trên A bằng nhau, thì giữ lại điểm đang xét.

Mã nguồn

void
Mathematics::doErosion (const Mat &srcImg, Mat &destImg, Point * kernelIndex, const Mat &kernel)
{
    destImg.setTo(Scalar(0.0));

    for (int idxRowImg = 0 ; idxRowImg < srcImg.size().height; idxRowImg++)
    {
        for (int idxColImg = 0; idxColImg < srcImg.size().width; idxColImg++)
        {
            if (match (srcImg, Point(idxColImg, idxRowImg), kernelIndex, kernel))
                destImg.at<unsigned char>(idxRowImg, idxColImg) = 255;
        }
    }
}

bool
Mathematics::match (const Mat &srcImg, Point2d pointAt, Point * kernelIndex, const Mat &kernel)
{
    double idxRowImg, idxColImg;
    int    idxKerIndex;
    idxKerIndex = -1;

    for (int idxRowKer = 0; idxRowKer < kernel.size().height; idxRowKer++)
    {
        for (int idxColKer = 0; idxColKer < kernel.size().width; idxColKer++)
        {
            idxKerIndex++;
            if (kernel.at<unsigned char>(idxRowKer, idxColKer) == 1)
            {
                idxRowImg = pointAt.y + kernelIndex[idxKerIndex].y;
                idxColImg = pointAt.x + kernelIndex[idxKerIndex].x;

                if (idxRowImg > srcImg.size().height - 1)
                    continue;
                if (idxRowImg < 0)
                    continue;
                if (idxColImg > srcImg.size().width - 1)
                    continue;
                if (idxColImg < 0)
                    continue;

                if (srcImg.at<unsigned char>(idxRowImg, idxColImg) !=  255)
                    return false;
            }
        }
    }
    return true;
}

Dòng 16 - 48: Hàm kiểm tra các điểm thuộc về phần tử cấu trúc - kernel (value = 1) có là tập con của đối tượng hay không.

pointAt: tọa độ (chỉ số dòng, chỉ số cột) của điểm đang xét.

kernelIndex: chỉ số truy cập nhanh đến kernel.

kernel: ma trận phần tử cấu trúc.

Hàm thực hiện duyệt ma trận kernel, với các điểm thuộc phần tử cấu trúc (value = 1), kiểm tra tại điểm tương ứng trên ảnh, nếu giá trị là background (!255) thì kết luận không phải tập con của đối tượng. Duyệt hết kernel, kết luận phần tử cấu trúc là tập con của đối tượng.

Hàm thư viện openCV:

void erode(InputArray src, OutputArray dst, InputArray kernel, Point anchor=Point(-1,-1), int iterations=1, int borderType=BORDER_CONSTANT, const Scalar& borderValue=morphologyDefaultBorderValue() )

Trong đó:

  • Src: ảnh nguồn.
  • Dst: ảnh kết quả.
  • Kernel: phần tử cấu trúc.
  • Anchor: điểm gốc của phần tử cấu trúc.
  • Interations: số lần thực hiện erosion liên tiếp cho ảnh nguồn.

Binary Dilation

Toán tử giãn nhị phân (binary dilation) có tác dụng làm tăng kích thước đối tượng, nối đứt đoạn, lấp lỗ hổng.

Minh họa

Trái: ảnh gốc. Phải: ảnh kết quả với ksize (3, 3); anchor point = default; shape = RECT

ss_8_text   ss_9_text_dilated

Định nghĩa

ss_10_Eqn_Erosion

Giải thích:

ss_11_SE :tập đối xứng qua gốc tọa độ của SE. Tập này được tịnh tiến theo một vector w bất kỳ, nếu tập này và A có ít nhất một điểm giao, thì giữ lại w, đưa vào kết quả.

Theo suy nghĩ lập trình: duyệt qua tất cả các điểm trong A, tại mỗi điểm, đặt anchor point của SE tại điểm đang xét, kiểm tra nếu tồn tại một điểm trong SE (giá trị bằng 1) và  điểm tương ứng trên A bằng nhau, thì giữ lại điểm đang xét.

Mã nguồn

void
Mathematics::doDilation(const Mat &srcImg, Mat &destImg, Point * kernelIndex, const Mat &kernel)
{
    srcImg.copyTo(destImg);
    
    int idxKer, idxRowKer, idxColKer, m, n;
    int lenKer = kernel.size().height * kernel.size().width;

    for (int idxRowImg = 0 ; idxRowImg < srcImg.size().height; idxRowImg++)
    { 
        for (int idxColImg = 0; idxColImg < srcImg.size().width; idxColImg++)
        {
            for (idxKer = 0; idxKer < lenKer; idxKer++)
            {
                idxRowKer = idxKer / kernel.size().width;
                idxColKer = idxKer % kernel.size().width;
                if (kernel.at<unsigned char>(idxRowKer, idxColKer) == 1)
                {
                    m = idxRowKer + kernelIndex[idxKer].y;
                    n = idxColKer + kernelIndex[idxKer].x;

                    if (m > srcImg.size().height - 1)
                        continue;
                    if (m < 0)
                        continue;
                    if (n > srcImg.size().width - 1)
                        continue;
                    if (n < 0)
                        continue;

                    if (scrImg.at<unsigned char>(m, n) == 255)
                    {
                        destImg.at<unsigned char>(idxRowImg, idxColImg) = 255;
                        break;
                    }
                }
            }
        }
    }
}

 

Hàm thư viện openCV:

void dilate(InputArray src, OutputArray dst, InputArray kernel, Point anchor=Point(-1,-1), int iterations=1, int borderType=BORDER_CONSTANT, const Scalar& borderValue=morphologyDefaultBorderValue())

Trong đó:

  • Src: ảnh nguồn.
  • Dst: ảnh kết quả.
  • Kernel: phần tử cấu trúc.
  • Anchor: điểm gốc của phần tử cấu trúc.
  • Interations: số lần thực hiện dilation liên tiếp cho ảnh nguồn.

Do chỉ sử dụng một cấu trúc phần tử duy nhất cho toàn bộ đối tượng trong ảnh, nên đối tượng sẽ giãn nở đều. Tuy nhiên, một số trường hợp như nhiễu, hoặc phần chi tiết người dùng không muốn bị giãn theo phép dilation, thì toán tử giãn nở không linh hoạt, cứng nhắc.

Binary Opening

Bởi vì việc sử dụng riêng lẻ toán tử giãn nhị phân và co nhị phân gây cứng nhắc, không linh hoạt theo ý người sử dụng. Việc kết hợp và tạo ra toán tử mở nhị phân giải quyết một số trường hợp như: muốn giãn nở chi tiết quan trọng, nhưng loại bỏ chi tiết thừa hoặc nhiễu (giãn nhị phân không làm được điều này). Hoặc chỉ xoá nhiễu, nhưng kích thước đối tượng không thay đổi (co nhị phân không làm được điều này).

Toán tử mở giúp làm trơn biên đối tượng, loại bỏ eo hẹp (đối với những eo có kích thước nhỏ hơn phần tử cấu trúc), và loại bỏ thành phần lồi mỏng. Đồng thời, khắc phục nhược điểm của các toán tử đơn.

Định nghĩa

ss_13_Eqn_Erosion

Mã nguồn

void
Mathematics::doOpening(const Mat &srcImg, Mat &destImg, Point * kernelIndex, const Mat &kernel)
{
    Mat temp = Mat(Size(srcImg.size()), CV_8UC1);
    doErosion(srcImg, temp, kernelIndex, kernel);
    doDilation(temp, destImg, kernelIndex, kernel);
}

Binary Closing

Xoá nhiễu, làm mất khuyết điểm trong đối tượng. Lấp đầy lỗ hổng ở viền đối tượng. Sự kết hợp toán tử co và giãn khắc phục nhược điểm của việc sử dụng từng toán tử đơn.

Định nghĩa

ss_14_Eqn_Erosion

Mã nguồn

void Mathematics::doClosing(const Mat &srcImg, Mat &destImg, Point * kernelIndex, const Mat &kernel)
{
    Mat temp = Mat(Size(srcImg.size()), CV_8UC1);
    doDilation(srcImg, temp, kernelIndex, kernel);
    doErosion(temp, destImg, kernelIndex, kernel);
}

Skeleton (toán tử khung xương)

Mục đích của toán tử rút xương là trích xuất hình dáng đặc trưng đại diện chung cho đối tượng.

Khái niệm skeleton được giới thiệu bởi H.Blum, là kết quả của Medial Axis Transform (MAT) hoặc Symmetry Axis Transform (SAT). MAT xác định số lượng điểm nằm trên biên của đối tượng mà gần nhất đến mỗi điểm thuộc đối tượng. Một điểm thuộc về khung xương nếu như điểm đó được MAT xác định có số lượng điểm lớn hơn 1.

ss_15_skeltouch

Ví dụ về minh hoạ cho điểm thuộc khung xương của đối tượng hình chữ nhật. Hai điểm A và B thuộc khung xương, tuy nhiên, điểm C không thuộc khung xương do chỉ có một điểm gần nhất nằm trên biên cạnh.

Toán tử rút xương có thể được biểu diễn bằng tập hữu hạn các phép co (erosion) mở (opening).

Định nghĩa

ss_16_Eqn

Với:

  • ss_17_Eqn
  • B là phần tử cấu trúc và ss_20_Eqn  là kết quả của phép thực hiện erosion k lần với B của A.

                ss_19_Eqn

  • K là lần thực hiện rút xương cuối cùng, mà bước tiếp theo ss_21_Eqn sẽ cho kết quả rỗng.

               ss_22_Eqn

Mã nguồn

void
Mathematics::skeleton(const Mat &srcImg, Mat &destImg, Point * kernelIndex, const Mat &kernel)
{
    Mat X_k = Mat(Size(srcImg.size()), CV_8UC1);
    srcImg.copyTo(X_k);

    Mat X_kSubOne = Mat::zeros(Size(srcImg.size()), CV_8UC1);

    Mat S_k = Mat(Size(srcImg.size()), CV_8UC1);
    Mat S_A = Mat::zeros(Size(srcImg.size()), CV_8UC1);
    Mat tempOpen = Mat(Size(srcImg.size()), CV_8UC1);

    doErosion(X_k, tempOpen, kernelIndex, kernel);

    while (sum(tempOpen)[0] != 0)
    {
        X_k.copyTo(X_kSubOne);
        doErosion(X_kSubOne, X_k, kernelIndex, kernel);

        doOpening(X_k, tempOpen, kernelIndex, kernel);
        tempOpen = 255 - tempOpen;
        bitwise_and(X_k, tempOpen, S_k);
        bitwise_or(S_A,S_k, S_A);

        doErosion(X_k, tempOpen, kernelIndex, kernel);
    }

    S_A.copyTo(destImg);
}

Toán tử rút xương được áp dụng thành công trong những ứng dụng y học:

  • Chuẩn đoán được triệu chứng hẹp thanh quản.
  • Chuẩn đoán được triệu chứng phình động mạch chủ dưới thận.
  • Phát hiện chứng đau đại tràng.

Lời kết

Hy vọng bài viết này sẽ giúp cho bạn hiện thực được giải thuật skeleton trong ảnh nhị phân. Nếu có thắc mắc hay vấn đề gì trong quá trình thực hiện, comment trực tiếp bên dưới hoặc có thể liên hệ với tôi.

THẢO LUẬN
ĐÓNG