Детектирование округлостей на изображении (на примере микрофотографий)

Всем привет! По своей профессии (строго говоря- будущей профессии) я вообще-то химик. Относительно недавно появилась интересная работа и объявилась необходимость много работать с цифровым микроскопом, делать большое количество фотографий и определённым образом их обрабатывать. А именно: находить линейные размеры частиц (чаще круглой формы и изначально- на глаз) и скрупулёзно заносить их в лабораторный журнал.
Неудивительно, что после первой же сотни изображений я крепко задумался о хоть какой-нибудь автоматизации этого процесса, но была одна загвоздка: я прекрасно знал, что «объектно-ориентированное программирование — это очень хорошо», но… Но я на тот момент владел только школьным TurboPascal, университетским VB и быдлокодингом на PHP в процедурном варианте. Потыкавшись по форумам, и учтя факт, что за день я успеваю поработать как минимум на двух ОС (Mac/Windows/Ubuntu существуют в эйфорическом симбиозе), я особо не задумывался и решил писать на Java.
Опуская подробности примерно недельной, в свободное от работы время, долбёжки своей головы об объектно-ориентированную парадигму программирования и бессонных ночей с мыслями наподобие «да как же, блин, это работает», я постараюсь максимально вкратце рассказать о том простом и быстром «алгоритме», который у меня родился. Стоит сразу сказать, что он годится только для достаточно четких изображений.
А вот, кстати, и типичный представитель (вернее, его примерно десятая часть), которого нужно обработать:



Сразу видно, что объекты — это окружности, и первое, что приходит в голову (да-да, спасибо университету, даже химики знают что это такое, и это действительно сразу же приходит в голову) — преобразование Хафа. Но… Опять «но»: объекты могут наезжать друг на друга, а также быть совершенно непохожими на окружности. Справедливости ради скажу, что я пробовал сделать это с помощью преобразования Хафа и библиотеки OpenCV на Python (здоровский язык) под Ubuntu… Пространство Хафа в этом случае получается слишком неоднозначным (== однородным) и за окружности принимается куча свободного места вокруг. Даже после предварительно выделенных границ в GIMP и прочих разных приёмов.

В общем, я решил написать свой почти велосипед. Итак, во-первых, нам нужно выделить границы. Попробовав несколько методов (их вообще-то не густо, так что, возможно, я попробовал их все), наиболее приемлемый результат давал метод «Canny Edge Detector» (как по-русски я не знаю, не бейте), и результат после этого получился такой:



После некоторого времени творческих мук, я наконец-то осознал, что области интереса — замкнуты. Вот только как выяснить, что эти точки образуют замкнутую кривую, и эти — нет? На обдумывание этого вопроса я потратил много времени, строил какие-то нечеловеческие выкладки, пытаясь применить тот математический аппарат, которому меня не так давно научили (а он оказался вполне качественным). И однажды меня осенило… Заливка!!! Нужно посмотреть, как работает инструмент «заливка» в графических Open Sourse проектах!!! Так я для себя открыл алгоритм Breadth-first search. Позже я всё-таки воспользовался для этих целей готовым классом, найденным на просторах интернета.
Вот так выглядит изображение после заливки:



Да! Мы выделили все интересующие нас объекты! Но только внутри них находятся какие-то непонятные штрихи. Только я начал думать, как же решить этот вопрос, и тут (прямо в тот же день) мне очень вовремя попадается статья на Хабрахабре про математическую морфологию (которая сейчас недоступна обычному пользователю). Сказано, сделано!
Вот так выглядит теперь наше изображение (метод «erode», матрицу взял стандартную крестообразную 3х3):



Ура! Готово! Теперь нам нужно ещё раз воспользоваться BFS-алгоритмом, и найти координаты центров и крайних точек наших частиц.
Итого получили почти готовую для использования программу для автоматических записей в журнал :) Т.к. от микроскопа идёт обычный usb-шнур, то очень хочется сразу в программе видеть изображение с камеры, тут же фотографировать и распознавать. Но это уже предмет моих следующих бессонных ночей.
А вот и конечный результат (кликабельно):

— 22.02.2011, 22:05 — перенёс в блог «обработка изображений»
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 38

    +3
    Можно было попробовать Матлабом с Image Processing Toolbox, или ImageJ
      +2
      Здесь как я понял задачка описать алгоритм и представить реализацию. С готовыми тулзами, ясен хобот, все проще :)
      +2
      У вас кое-где съелись внешние круги.

      А что, если разрыв будет сильнее?
        0
        Надо делать более умную заливку — чтобы не точка распространялась, а окружность определённого радиуса. Где она целиком пролезет — туда и зальёт.

        Автору по поводу «морфологий» — я бы порекомендовал не blur'ить результат, а построить дерево вложенности залитых областей, после чего оставить только самую внешнюю связную область (фон) и первичных потомков этого корня (волшебные пузырьки).
          0
          Да, если разрыв будет сильнее, то некоторые точки теряются. Я старался брать тестовые картинки с максимальным разнообразием частиц (по форме и размерам), и на них результат получился просто отличный. Но несколько фотографий через два дня показали, что нужно алгоритм совершенствовать: действительно часть областей получается совсем чуть-чуть разомкнутой, и они теряются.
          Я уже думал применить метод, похожий по существу на то, что предложил Harkonnen: с помощью той же математической морфологии замкнуть слегка разомкнутые границы. Но всё оказалось сложнее: плотность частиц может быть очень высокой, и вместе с нужными границами ещё выделяется много «мусора», в котором наш диск попросту застревает, приводя таким образом к обнаружению абсолютно «левых» частиц (которых на самом деле нет).
            0
            Примеры фоток и примеры результатов, может чего-то подскажем)
              0
              Добавил пример ещё одной фотографии в комментариях к такому же алгоритму для тех же целей в среде MATLAB.
          0
          Интересно и познавательно, спасибо, но а где программа? хотел почувствовать себя химиком :)
            +1
            А мне вот как не химику интересно, а что же за «волшебные пузырьки» на этих фотках?
              +4
              Сферические округлости в вакууме, разве не понятно?
                0
                Это инновации. И без всяких кавычек. Действительно.
                Если у меня получится автоматизировать процесс… Я не готов говорить что точно будет, но будет просто великолепно :)
              +12
              Эх, а я прочел анонс в твиттере, и на минутку помечтал, что в статье речь совсем о других «округлостях» пойдет…
                0
                Только тссс! А то борцы за духовную безопасность интернета возьмут на вооружение.
                  –1
                  Да-да. Последующая фраза про электронный микроскоп все испортила.
                    –1
                    Аналогично. Заходил в топик с намерением откомментировать пост соответствующей картинкой.
                      –1
                      Берем программу автора по детектированию округлостей, берем 3D-принтер, заправляем его силиконом — профитъ!
                      0
                      В нашей лабе один из студентов занимается подобными изысканиями. Направлю ка я ему эту ссылку. Одно плохо — он русского не знает… :) Он кстати тоже на Матлабе делает.
                        +2
                        Рекомендую не опираться на алгоритмы основанные на гистерезисе без лишней надобности (non-maximum suppression в canny edge detector'е).
                        Хоть вы и говорите что ваши объекты могут «быть совершенно непохожими на окружности», попробуйте сделать так:
                        1. Возьмите экземпляр объекта высокого разрешения (шаблон), примените к нему преобразование (о нем позже)
                        2. Для каждого квадратного окна входного изображения А. уменьшите его до размера шаблона и Б. посчитайте над ним тоже самое преобразование, а затем корреляцию результата и преобразованного шаблона. Если корреляция велика, то перед вами экземпляр объекта

                        Преобразование может быть например таким:
                        1. Перевод RGB-Luma
                        2. OutPix = dx*dx + dy*dy, где dx — это результат применения оператора Собеля по горизонтали (например с ядром 3х3), а dy — по вертикали. Таким образом в каждом пикселе будет записан квадрат производной по направлению, т.е. грубо говоря сила границы.
                          0
                          Класс! Надо обязательно осилить себя и сделать это! Большое спасибо за идею!
                            0
                            Для каждого квадратного окна? Я так понимаю нужно перебирать и позиции окна и размеры? Сразу встает вопрос — в каких границах размеры окна перебирать? Сколько все это будет по времени длится?
                            На лабах делали такое — очень плохо работало даже для обычных бинарных шаблонов типа самолет и колечко.
                            0
                            как насчёт пересекающихся кругов (т.е. если объекты «наложены»)?
                              0
                              Они не определяются. Или, вернее, если границы четкие, то конечно определяются, но ведь заодно я считаю площадь частицы, а также её полярные точки. Как из площади, так и из крайних точек я получаю значение диаметра окружности (из предположения, конечно, что это окружность), и если эти два диаметра отличаются не больше чем на 80%, то объект засчитывается. Если нет — отбрасывается.
                              0
                              о, пытаюсь решать похожую задачу, только каждая частица у меня представляет собой агрегат из нескольких слипшихся шариков.
                              и присоединяюсь к вопросу, что представляет из себя объект вашего исследования.
                                –20
                                Детектирование, блядь.
                                  0
                                  Детектирование циркулярностей на пикче. тоже вроде понятно)
                                  0
                                  >«Canny Edge Detector» (как по-русски я не знаю, не бейте)
                                    +2
                                    «хитрый определитель границ»
                                  +2
                                  >«Canny Edge Detector» — всего лишь детектор краев Канни, один из методов выделения границ
                                    +1
                                    Насчет заливки — я еще одну использовал для цифровой обработки изображений — заливка с затравкой, вот реализация на джаве pastebin.com/WaLgEEzr
                                      0
                                      Попробуйте натравить на сканы Плэйбоя — сколько округлостей найдет?:) А вообще спасибо, было интересно почитать.
                                        +4
                                        А на самом деле это же для поиска сисек, да?
                                          0
                                          Подобная задача встречается у микроскопистов, работающих с клетками. Нужно подсчитать общее количество клеток, количество окрашенных и т.д. При этом клетки хоть и округлые, но могу быть достаточно замысловатых форм, слипаться и т.д. Возможно, что в программах для биологов можно будет найти интересные алгоритмы.
                                            0
                                            Очень, очень интересная и актуальная статья! Про заливку и про этот алгоритм поиска в ширину расскажите пожалуйста, не соображу как задачу над изображением преобразовать к задаче над графом.
                                              0
                                              Довольно несложно: простым перебором всех точек (и их соседей) изображения. Для упрощения задачи изображение должно быть двуцветным. В качестве примера реализации можно привести код, предложенный alexeygrigorev, в этом комментарии.
                                              Как я и написал, для заливки я воспользовался готовым классом (они, кстати, очень похожи).
                                              Пользоваться им очень просто:

                                              FloodFill rere = new FloodFill(whereDetectToFillWhite); // whereDetectToFillWhite - объект java.awt.Image;
                                              Color white = new Color(255, 255, 255);
                                              rere.fill(1, 1, white); // Здесь вроде всё понятно: (икс_заливки, игрек_заливки, объект_цвета)
                                              Image whereDetectJustFilled = rere.getImage();
                                              0
                                              Спасибо, идею понял по исходникам, совсем забыл начала программирования.
                                              Я вот как придумал избавится от рваных контуров:
                                              1. Выделяем контура,
                                              2. Делаем Дилатацию — расширяем границы — скорее всего после этого контура соединятся, но станут толстыми.
                                              3. Потом делаем заливку — толстые и замкнутые контура не позволят залить объект.
                                              4. Потом по бинарному изображению опять выделяем контура — совсем простым образом, они вот эти уже контура не должна быть рваные.
                                              Предполагаемый недостаток — контур слегка сместится, но это не очень страшно, его потом можно уточнить.
                                              Как думаете — будет работать? Сейчас реализовываю потихонечку.
                                                0
                                                Я так уже пробовал, и уже писал здесь в комментариях. К сожалению, в моём случае это ведёт также к «обнаружению» несуществующих окружностей…

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое