Поиск особых точек на отпечатке пальца

Я пытаюсь написать программу, которая находит особые точки на отпечатке пальца.

Сначала я бинаризирую картинку.

private Bitmap binarization(Bitmap sourceBitmap)
        {
            Bitmap targetBitmap = new Bitmap(sourceBitmap.Width, sourceBitmap.Height);
            for (int y = 0; y < sourceBitmap.Height; ++y)
                for (int x = 0; x < sourceBitmap.Width; ++x)
                {
                    Color c = sourceBitmap.GetPixel(x, y);
                    byte rgb = (byte)(0.3 * c.R + 0.59 * c.G + 0.11 * c.B);
                    targetBitmap.SetPixel(x, y, Color.FromArgb(c.A, rgb, rgb, rgb));
                }
            return targetBitmap;
        }

Затем я скелетизирую изображение (я использую алгоритм Zhang-Suen, который я взял вот тут https://stackoverflow.com/questions/20245003/zhang-suen-thinning-algorithm-c-sharp)

public static T[][] ArrayClone<T>(T[][] A)
        { return A.Select(a => a.ToArray()).ToArray(); }

        public static bool[][] ZhangSuenThinning(bool[][] s)
        {
            bool[][] temp = ArrayClone(s); 
            int count = 0;
            do  
            {
                count = step(1, temp, s);
                temp = ArrayClone(s);      
                count += step(2, temp, s);
                temp = ArrayClone(s);      
            }
            while (count > 0);
            return s;
        }

        static int step(int stepNo, bool[][] temp, bool[][] s)
        {
            int count = 0;

            for (int a = 1; a < temp.Length - 1; a++)
            {
                for (int b = 1; b < temp[0].Length - 1; b++)
                {
                    if (SuenThinningAlg(a, b, temp, stepNo == 2))
                    {
                        if (s[a][b]) count++;
                        s[a][b] = false;
                    }
                }
            }
            return count;
        }

        static bool SuenThinningAlg(int x, int y, bool[][] s, bool even)
        {
            bool p2 = s[x][y - 1];
            bool p3 = s[x + 1][y - 1];
            bool p4 = s[x + 1][y];
            bool p5 = s[x + 1][y + 1];
            bool p6 = s[x][y + 1];
            bool p7 = s[x - 1][y + 1];
            bool p8 = s[x - 1][y];
            bool p9 = s[x - 1][y - 1];


            int bp1 = NumberOfNonZeroNeighbors(x, y, s);
            if (bp1 >= 2 && bp1 <= 6) 
            {
                if (NumberOfZeroToOneTransitionFromP9(x, y, s) == 1)
                {
                    if (even)
                    {
                        if (!((p2 && p4) && p8))
                        {
                            if (!((p2 && p6) && p8))
                            {
                                return true;
                            }
                        }
                    }
                    else
                    {
                        if (!((p2 && p4) && p6))
                        {
                            if (!((p4 && p6) && p8))
                            {
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

        static int NumberOfZeroToOneTransitionFromP9(int x, int y, bool[][] s)
        {
            bool p2 = s[x][y - 1];
            bool p3 = s[x + 1][y - 1];
            bool p4 = s[x + 1][y];
            bool p5 = s[x + 1][y + 1];
            bool p6 = s[x][y + 1];
            bool p7 = s[x - 1][y + 1];
            bool p8 = s[x - 1][y];
            bool p9 = s[x - 1][y - 1];

            int A = Convert.ToInt32((!p2 && p3)) + Convert.ToInt32((!p3 && p4)) +
                    Convert.ToInt32((!p4 && p5)) + Convert.ToInt32((!p5 && p6)) +
                    Convert.ToInt32((!p6 && p7)) + Convert.ToInt32((!p7 && p8)) +
                    Convert.ToInt32((!p8 && p9)) + Convert.ToInt32((!p9 && p2));
            return A;
        }
        static int NumberOfNonZeroNeighbors(int x, int y, bool[][] s)
        {
            int count = 0;
            if (s[x - 1][y]) count++;
            if (s[x - 1][y + 1]) count++;
            if (s[x - 1][y - 1]) count++;
            if (s[x][y + 1]) count++;
            if (s[x][y - 1]) count++;
            if (s[x + 1][y]) count++;
            if (s[x + 1][y + 1]) count++;
            if (s[x + 1][y - 1]) count++;
            return count;
        }

Теперь я пытаюсь выделить особые точки. Если вокруг точки есть только один(или их нет вообще) черный пиксель, то это конечная точка. Это у меня получилось.

Конечные точки отмечены красным

Теперь мне нужно найти точки ветвления, то есть точки, вокруг которых есть 3 черных пикселя. Я получаю вот такой неверный результат:

Точки ветвления отмечены фиолетовым

Это получается потому что после скелетизации картинки остаются лишние(или не лишние?) черные пиксели, которые я считаю как дополнительные отростки.

Результат скелетизации

Вот код поиска особых точек. findCheckPoint(Bitmap img) обходит все точки картинки, а checkThisPoint(Bitmap img, int x, int y) проверяет количество черных пикселей вокруг каждой точки.

private int checkThisPoint(Bitmap img, int x, int y)
        {
            int c = 0;
            for (int i = x - 1; i < x + 2; i++)
            {
                for (int j = y - 1; j < y + 2; j++)
                {
                    if (img.GetPixel(i, j) == Color.FromArgb(0, 0, 0))
                        c++;
                }
            }
            return c - 1;
        }
private List<List<int>> findCheckPoint(Bitmap img)
        {
            int x = img.Width;
            int y = img.Height;
            List<int> branchPointX = new List<int>();
            List<int> branchPointY = new List<int>();
            List<int> endPointX = new List<int>();
            List<int> endPointY = new List<int>();
            for (int i = 0; i < x; i++)
            {
                for (int j = 0; j < y; j++)
                {
                    int t;
                    if (img.GetPixel(i, j) == Color.FromArgb(0, 0, 0))
                    {
                        t = checkThisPoint(img, i, j);
                        if (t <= 1)
                        {
                            endPointX.Add(i);
                            endPointY.Add(j);
                        }
                        if(t == 3)
                        {
                            branchPointX.Add(i);
                            branchPointY.Add(j);
                        }
                    }

                }
            }
            List<List<int>> a = new List<List<int>>();
            a.Add(endPointX);
            a.Add(endPointY);
            a.Add(branchPointX);
            a.Add(branchPointY);
            return a;
        }

Я не знаю как решить эту проблему. Нужно как то переделать алгоритм скелетизации(если да, то как?), или по другому искать особые точки? Пробовал рассматривать область большую, чем 3 * 3, но это результата не дало.

UPD

Отпечаток, использованный в программе. Отпечаток


Ответы (1 шт):

Автор решения: Arcanecliff

Решил данную проблему.

Последовав совету @aepot, рассмотрел матрицу 5x5, где в центре исследуемый пиксель. Но получилось так, что если на границах более 2 черных пикселей, то это не гарантирует то, что этот пиксель является точкой ветвления.

Пример: НЕ точка ветвления На границах 4 черных пикселя, но это не точка ветвления.

Тогда я понял, что нужно считать количество подпоследовательностей единичек в последовательности всех пикселей границ матрицы.(С учетом того что длина подпоследовательности может быть равная 1)

То есть для вышеприведенного примера последовательность всех пикселей границ будет такой :Последовательность

Учитывая то, что продолжение подпоследовательности единиц может находится в начале основной последовательности(как в этом примере) написал такой код:

int indexFirstZero = ArrayPoint.IndexOf(0);
for (int i = indexFirstZero + 1; i < ArrayPoint.Count; i++)
            {
                bool stopFlag = false;
                if (ArrayPoint[i] == 1)
                {
                    count++;
                    while(ArrayPoint[i] != 0)
                    {
                        if(i == ArrayPoint.Count - 1)
                        {
                            i = 0;
                            stopFlag = true;
                        }
                        else
                            i++;
                    }
                    if (stopFlag)
                        break;
                }
            }            

Тут, count - количество подпоследовательностей единичек.

Теперь, вроде как, работает. Точки ветвления отмечены синим

Вот весь код.

private int checkThisPointBranch(Bitmap img, int x, int y)
        {
            int count = 0;
            int[, ] tempMatrix = new int[5, 5];

            // Выделение матрицы 5x5.
            int q = -1, k = -1;
            for (int i = x - 2; i < x + 3; i++)
            {
                q++;
                k = -1;
                for (int j = y - 2; j < y + 3; j++)
                {
                    k++;
                    tempMatrix[q, k] = img.GetPixel(i, j) == Color.FromArgb(0, 0, 0) ? 1 : 0;
                }
            }

            // Выделение границы для последовательности.
            List<int> ArrayPoint = new List<int>();
            for (int i = 1; i < 5; i++)
                ArrayPoint.Add(tempMatrix[0, i]);
            for (int i = 1; i < 5; i++)
                ArrayPoint.Add(tempMatrix[i, 4]);
            for (int i = 3; i >= 0; i--)
                ArrayPoint.Add(tempMatrix[4, i]);
            for (int i = 3; i >= 0; i--)
                ArrayPoint.Add(tempMatrix[i, 0]);

            // Поиск подпоследовательностей единиц.
            int indexFirstZero = ArrayPoint.IndexOf(0);
            for (int i = indexFirstZero + 1; i < ArrayPoint.Count; i++)
            {
                bool stopFlag = false;
                if (ArrayPoint[i] == 1)
                {
                    count++;
                    while(ArrayPoint[i] != 0)
                    {
                        if(i == ArrayPoint.Count - 1)
                        {
                            i = 0;
                            stopFlag = true;
                        }
                        else
                            i++;
                    }
                    if (stopFlag)
                        break;
                }
            }            
            return count;
        }
→ Ссылка