5

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

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

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

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

4
  • Дискретный анализ изображения вам ничего не даст, то есть подсчет соседей. Как минимум потому что все изображения разные и как алгоритм воедет себя на какой-то другой картинке - неизвестно. Лично я не считаю ту единичку, на которую вы ругаетесь лишней. По вашей логике у течки должно быть не больше 2 соседей в матрице 3x3, и это условие выполняется. При ветвлении у точки, которая является центром матрицы 3x3 должно быть 3 соседа, по идее не смежных друг с другом. А потом, откуда вы знаете, что это не реальное ветвление, длина ветки которого всего 1 пиксель?
    – aepot
    2 апр 2021 в 14:30
  • 1
    Возмите матрицу 5x5, если ветвление в 1 пиксель для вас - мало, смотрите длину веток. Если в границу матрицы 5x5 упирается более 2 черных пикселей - нужная точка найдена.
    – aepot
    2 апр 2021 в 14:36
  • Кстати, у вас есть оригинальный снимок отпечатка? Не чищеный, не фильтрованый, исходный. Хочу на выходных попробовать другой алгоритм. Вдруг что получится.
    – aepot
    2 апр 2021 в 14:43
  • 1
    Добавил использующийся отпечаток, если что то получится с другим алгоритмом - пожалуйста свяжитесь со мной. Насчет проверки матрицы 5 x 5 - буду пробовать, если что то получится - добавлю в тему. 2 апр 2021 в 15:08

1 ответ 1

2

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

Последовав совету @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;
        }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.