Практическое применение алгоритма заливки

Вот в чем проблема: у вас есть предметное стекло (как показано ниже), содержащее сотни клеток. У вас также есть наборы связанных данных, таких как концентрация кислорода в каждом месте на слайде.

Чтобы осмысленно обрабатывать эти связанные данные в контексте ячеек на слайде, вам необходимо знать расположение каждой ячейки на слайде, чтобы ее можно было сопоставить с соответствующей концентрацией кислорода в ее местоположении.

Ручной подход

Вы можете пойти дальше и визуально отметить расположение каждой ячейки на слайде вручную. Затем вы можете сопоставить каждую идентифицированную ячейку с ее местоположением в соответствующем наборе данных и таким образом собирать концентрации кислорода.

Однако у этого есть два непосредственных недостатка:

  1. Отметка расположения 200 ячеек занимает много времени, а делать это для сотен слайдов неразумно.
  2. Это не очень точно. Человек приблизил бы местоположение клетки к одной точке, тогда как в действительности каждая клетка охватывает часть клетки различной формы и размера. Это проблематично, если вы хотите изучить взаимосвязь между местоположением клетки и другой переменной, такой как концентрация кислорода, потому что местоположение клетки не будет достаточно точным.

Лучше: автоматизированный подход

Решением этих двух недостатков ручной маркировки ячеек является автоматизация процесса. Этого можно было бы добиться, применив более сложные методы машинного зрения, но вместо этого я решил использовать более простой подход, основанный на алгоритме заполнения заливкой. Я выбрал этот подход, потому что считаю, что если более простой подход работает так, как вам нужно, вы должны использовать его.

Для ясности давайте посмотрим, чего мы хотим достичь в конце дня:

Цель алгоритма

В качестве входных данных: файл изображения, содержащий несколько ячеек. Создать в качестве вывода: список ячеек изображения, каждая из которых представлена ​​списком местоположений в пикселях, которые она занимает

Решение более простой задачи

Настоящий слайд клеток ставит много проблем:

  1. Присутствует шум, означающий, что на «фоне» изображения появляются объекты, отличные от клеток.
  2. Клетки имеют необычную форму и иногда соприкасаются друг с другом.

Чтобы решить суть проблемы, не беспокоясь об этих проблемах, давайте сделаем слайд «идеальный мир» из ячеек:

Теперь с ним будет намного проще работать, чем с первым показанным примером, потому что нам не придется беспокоиться о фильтрации/предварительной обработке изображения. Чтобы по существу сгруппировать цветные пиксели вместе, мы можем использовать алгоритм под названием заливка заливкой.

Алгоритм заливки

Хороший способ визуализировать заливку — подумать об инструменте ведро с краской в ​​приложении для рисования. По сути, он наливает краску на определенную область цвета, останавливаясь на границе, где цвет меняется. Как вы можете себе представить, мы могли бы использовать эту технику для решения нашей проблемы: налить черный цвет на каждый цветной пиксель; все пиксели, которые мы в конечном итоге окрашиваем, являются частью этой ячейки.

Заливка работает, проверяя начальный пиксель и закрашивая этот пиксель новым цветом, если это необходимо. Затем он снова рекурсивно вызывает заливку для четырех окружающих пикселей. Базовая реализация заливки, которая берет все нечерные пиксели в начальной области и делает их черными (как окрашивание красных ячеек в черный цвет на изображении выше). В этом примере image — это матрица (двухмерный список) чисел с плавающей запятой, представляющих значения пикселей в изображении в градациях серого.

def flood_fill(x, y, width, height):
  """
  x: starting pixel row index
  y: starting pixel column index
  width: the width of the image
  height: the height of the image
  Blackens all non-black pixels in the same region as the starting
  pixel
  """
  # Base Case: the cell is already black
  if image[x][y] == 0:
    return
  # Recursive Case: the cell is not black
  image[x][y] = 0
  # Invoke flood fill on all surrounding cells:
  if x > 0:
    flood_fill(x - 1, y)
  if x + 1 < width:
    flood_fill(x + 1, y)
  if y > 0:
    flood_fill(x, y - 1)
  if y + 1 < slide.height:
    flood_fill(x, y + 1)

В нашем случае мы хотим немного расширить заливку, что позволит нам отслеживать, какие ячейки мы раскрасили, поскольку в конечном итоге это и есть наша цель: узнать, какие пиксели являются частью конкретной ячейки. на изображении. Это можно сделать несколькими способами, но я решил сделать это, определив внутреннюю функцию для заливки заливкой и заставив ее добавлять местоположение пикселя в список каждый раз, когда он окрашивает пиксель.

def explore_cell(self, slide, base_x, base_y):
  '''
  Finds all pixels that are part of the cell that contains 
  the base pixel
  :param slide: the slide to search
  :param base_x: the X coordinate of any pixel contained in the cell
  :param base_y: the Y coordinate of any pixel contained in the cell
  :returns pixels: the pixels that cover the cell containing the
                   base pixel
  '''
  cell_pixels = []
  def flood_fill(x, y):
    if slide[x][y] == 0:
      return
    cell_pixels.append((x, y))
    slide[x][y] = 0
    # Invoke flood fill on all surrounding cells:
    if x > 0:
       flood_fill(x - 1, y)
    if x + 1 < len(slide[0]):
       flood_fill(x + 1, y)
    if y > 0:
       flood_fill(x, y - 1)
    if y + 1 < len(slide):
       flood_fill(x, y + 1)
  flood_fill(base_x, base_y)
return cell_pixels

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

Возвращение к исходной проблеме

Вышеупомянутое решение для заполнения заливки отлично работает для упрощенных примеров, таких как тот, который я создал. Однако в реальном мире нам приходится иметь дело с шумом и ячейками странной формы. Если мы запустим наш вышеприведенный код, например, на реальном слайде, он достигнет предела глубины рекурсии и вылетит, потому что он продолжает раскрашивать все изображение, думая, что шум является частью ячейки. Чтобы заставить это решение работать, нам придется немного почистить.

Фильтрация изображения

Я пришел к следующему процессу фильтрации путем проб и ошибок в сочетании с обычными методами работы с подобным шумом.

Преобразование в оттенки серого

  1. Чтобы начать процесс фильтрации, мы преобразуем изображение в оттенки серого, чтобы упростить задачу и не беспокоиться о трех цветовых каналах. Мы можем просто усреднить три цвета, чтобы добиться этого.

Применение гейта

Поскольку в изображении все еще есть шум, мы можем затем применить простой шумоподавитель. Для этого мы в основном рассматриваем каждый пиксель, и если он ниже определенного порогового значения (например, 0,1), когда мы устанавливаем его равным нулю. В противном случае мы устанавливаем его равным 1. Это помогает избавиться от фонового шума с низкой амплитудой в изображении. Кроме того, это значительно упрощает изображение, делая каждый пиксель в основном логическим, поэтому нам не нужно учитывать разницу между светло-серой и темно-серой ячейкой.

Фильтр размера ячейки

На изображении по-прежнему присутствует куча отдельных пикселей или групп из нескольких пикселей, которые являются результатом сильного шума, который не был удален простым шумоподавителем. Чтобы исправить это, мы можем отфильтровать по размеру ячейки и, по сути, сказать, что любая ячейка размером менее 5 пикселей или около того на самом деле не является ячейкой. Результат этого таков:

На данный момент изображение достаточно чистое, чтобы наш оригинальный подход мог его обработать.

Результаты

У меня было несколько примеров слайдов, которые я пересчитал вручную, и результаты были довольно положительными. Он обнаружил около 98% ячеек, и визуально вы можете видеть, что он точно определяет правильную форму ячеек, что хорошо для подробного анализа данных, собранных о ячейках, на уровне пикселей.

Вывод

Чтобы решить эту проблему обнаружения клеток на зашумленном изображении слайда, я сначала превратил ее в более легкую задачу, которую я мог решить. Я использовал существующий алгоритм (заливка) для решения этой проблемы и предпринял шаги (фильтрацию), чтобы сделать это решение применимым к реальной проблеме, с которой я столкнулся.

В целом, это была хорошая проблема, которую нужно было решить, и я рад, что ко мне обратились с ней. Я надеюсь, что то, что я делюсь этим здесь, в некотором роде вдохновляет. Посмотреть репозиторий можно здесь.

Ваше здоровье!