• Home »
  • Cao học »
  • Một số kỹ thuật trong bài toán xử lý ảnh – Giải thuật gán nhãn các thành phần liên thông

Một số kỹ thuật trong bài toán xử lý ảnh – Giải thuật gán nhãn các thành phần liên thông


     Giải thuật gán nhãn các thành phần liên thông, mỗi thành phần liên thông được gán một nhãn duy nhất dựa vào một heuristic.
Để xác định thành phần liên thông trên một ảnh, ta nhóm các điểm ảnh vào các thành phần dựa vào tính kết nối của các điểm ảnh. Tất cả các điểm ảnh trong một thành phần liên thông cùng chia sẻ các giá trị điểm ảnh tương tự nhau và có đường đi giữa hai điểm bất kỳ.
Khả năng liên thông có thể được sử dụng: liên thông 4 hoặc liên thông 8.

Hinh 1 - LienThong
Hình 1 : Các khả năng liên thông được sử dụng

Thuật toán:
 Đầu vào:
 Ma trận điểm ảnh : data
 Đầu ra:
 Ma trận nhãn : labels

Thuật toán duyệt hai lần:

     Việc gán nhãn các thành phần liên thông được thực hiện bằng cách quét ảnh theo từng điểm ảnh một (từ trên xuống dưới, từ trái qua phải) để xác định các vùng điểm ảnh liên thông. Đó là các vùng của các điểm ảnh kề nhau với cùng tập giá trị điểm ảnh V. (Với ảnh nhị phân V={1}, tuy nhiên với ảnh xám, V sẽ chiếm một giải các giá trị,
vd: V={51,52,53,…,77,78,79,80}).
Giải thuật gán nhãn các thành phần liên thông có thể sử dụng cho các ảnh nhị phân hoặc ảnh xám. Tuy nhiên sau đây chúng ta giả sử các ảnh đầu vào là ảnh nhị phân và sử dụng liên thông 8. Giải thuật bao gồm hai lần duyệt, mỗi lần lặp qua 2 chiều của ảnh đầu vào. Lần duyệt thứ nhất để ghi nhận các lớp tương đương và gán các nhãn tạm. Lần duyệt thứ hai để thay thế các nhãn tạm thời bởi nhãn của lớp tương đương.

Lần duyệt thứ nhất:

1.Duyệt qua từng điểm ảnh p theo cột, sau đó theo hàng
2.Nếu V(p) ={1}
• Kiểm tra 4 điểm kề của p mà đã được duyệt qua trong quá trình quét (điểm bên trái, bên trên, điểm ở góc trên trái, điểm ở góc trên phải).
• Nếu tất cả 4 điểm kề này là 0, gán một nhãn mới cho p, ngược lại thực hiện bước tiếp theo
• Nếu duy nhất một điểm kề có V={1}, gán nhãn của điểm đó cho p, ngược lại thực hiện bước tiếp theo
• Nếu nhiều hơn một điểm kề có V={1}, gán một trong số các nhãn của 4 điểm đó cho p và lưu trữ lại sự tương đương giữa các nhãn.
3.Sắp xếp các cặp nhãn tương đương thành các lớp tương đương và gán một nhãn duy nhất cho mỗi lớp.

Lần duyệt thứ hai:

1.Duyệt qua từng điểm ảnh p theo cột sau đó theo hàng
2.Nếu V(p)={1}
Gán lại nhãn cho p theo nhãn của lớp tương đương
Minh họa:
Ảnh gốc ban đầu :

Hinh 2 - Lien Thong

Hình 2: Ảnh gốc trước khi áp dụng twopass

Sau lần duyệt đầu tiên, có 7 nhãn được sinh ra :

Hinh 3 - Lien Thong

Hinh 3 : Ảnh sau lần duyệt đầu tiên

Và ta thu được các nhãn tương đương:

Tập Các nhãn tương đương
Tập 1 1,2
Tập 2 1,2
Tập 3 3,4,5,6,7
Tập 4 3,4,5,6,7
Tập 5 3,4,5,6,7
Tập 6 3,4,5,6,7
Tập 7 3,4,5,6,7

Bảng 1: Bảng tập các nhãn thu được sau lần duyệt đầu tiên.

Sau lần duyệt thứ hai, các nhãn tạm sẽ được thay bởi nhãn của các lớp tương đương:

Hinh 4 - Lien Thong
Hình 4 : Nhãn của các điểm ảnh sau lần duyệt thứ 2 của twopass

Độ phức tạp của thuật toán: O(n2)

Giả mã:

{Ở đây ta coi màu nền: 0, màu của đối tượng : 1}
Function  CCL(data: Ma trận ảnh)
Begin
	linked =  
	labels :=  {Nhãn của các điểm ảnh}

	{Lần duyệt đầu tiên}
	For row:=1 to m do
		For column:=1 to n do
		If data[row][col] !=0 then
		Begin
		          neighbors = {Tập điểm liên thông với điểm hiện tại}
		          If neighbors =   then
				linked[NextLabel] := {NextLabel}
				labels[row][column] := NextLabel
				NextLabel += 1
		          Else
		         {Tìm nhãn nhỏ nhất}
				L := {Các nhãn liền kề}
				labels[row][column] := min(L)
				Foreach label in L
				linked[label] := linked[label]  L
		End;

	{Lần duyệt thứ hai}
	For row:=1 to n do
		For colum:=1 to n do
			If labels[row][column] !=0 then
				labels[row][col] = find(labels[row][col])

	return labels
End;

Cài đặt thuật toán C#:

public class ConnectedComponentLabeling
    {

        private int[,] _board;
        private int _width;
        private int _height;

        public ConnectedComponentLabeling(int[,] pInput)
        {
            _board = pInput;
            _width = _board.GetLength(0);
            _height = _board.GetLength(1);
        }
        /// 
        /// 
        /// 
        /// Ma trận ảnh nhị phân đầu vào, 0 là nền , 1 là đối tượng
        public void FindConnectedComponentLabeling()
        {

            // Duyệt vòng 1 để tìm ra tập nhãn liên thông.
            int labelCount = 1;
            var allLabels = new Dictionary();
            for (int rIndex = 0; rIndex < _width; rIndex++)
                for (int cIndex = 0; cIndex < _height; cIndex++)
                {
                    if (_board[rIndex, cIndex] != 0)
                    {
                        IEnumerable neighboringLabels = GetNeighboringLabels(rIndex, cIndex);
                        int currentLabel;

                        if (!neighboringLabels.Any())
                        {
                            currentLabel = labelCount;
                            allLabels.Add(currentLabel, new Labeling(currentLabel));
                            labelCount++;
                        }
                        else
                        {
                            currentLabel = neighboringLabels.Min(n => n);
                            Labeling root = allLabels[currentLabel].GetRoot();

                            foreach (var neighbor in neighboringLabels)
                            {
                                if (root.Name != allLabels[neighbor].GetRoot().Name)
                                {
                                    allLabels[neighbor].Join(allLabels[currentLabel]);
                                }
                            }
                        }

                        _board[rIndex, cIndex] = currentLabel;
                    }
                }

            for (int rIndex = 0; rIndex < _width; rIndex++)
                for (int cIndex = 0; cIndex < _height; cIndex++)
                {
                    int patternNumber = _board[rIndex, cIndex];
                    if (patternNumber != 0)
                    {
                        _board[rIndex, cIndex] = allLabels[patternNumber].GetRoot().Name;
                    }
                }
        }

        /// 
        /// Tìm 4 các láng giềng của điểm đang xét có tọa độ (x,y)
        /// 
        /// 
        /// 
        /// 
        private IEnumerable GetNeighboringLabels(int pRowIndex, int pColIndex)
        {
            var neighboringLabels = new List();

            if (pColIndex - 1 >= 0 && _board[pRowIndex, pColIndex - 1] > 0)
            {
                neighboringLabels.Add(_board[pRowIndex, pColIndex - 1]);
            }

            if (pRowIndex - 1 >= 0 && pColIndex - 1 >= 0 && _board[pRowIndex - 1, pColIndex - 1] > 0)
            {
                neighboringLabels.Add(_board[pRowIndex - 1, pColIndex - 1]);
            }

            if (pRowIndex - 1 >= 0 && _board[pRowIndex - 1, pColIndex] > 0)
            {
                neighboringLabels.Add(_board[pRowIndex - 1, pColIndex]);
            }

            if (pRowIndex - 1 >= 0 && pColIndex + 1 < _height && _board[pRowIndex - 1, pColIndex + 1] > 0)
            {
                neighboringLabels.Add(_board[pRowIndex - 1, pColIndex + 1]);
            }
            return neighboringLabels;
        }
    }

Liên hệ:
Bạn đọc quan tâm có thể gửi yêu cầu về email : [email protected]

Phản hồi