Генетический алгоритм для сегментаций строк в рукописном документе / Хабр

Генетический алгоритм для сегментаций строк в рукописном документе / Хабр

Генетический алгоритм (GA)

Генетический алгоритм – это классический эволюционный алгоритм, основанный на случайной переборе параметр. Под случайным здесь мы подразумеваем, что для поиска решения с использованием ГА, случайные изменения применялись к текущим решениям для генерации новых. GA основан на теории эволюции Дарвина. Это медленный постепенный процесс, который работает путем внесения небольших и медленных изменений. Кроме того, GA медленно вносит небольшие изменения в свои решения, пока не получит лучшее решение. Подробнее можете узнать здесь

Цель

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

Рис. 1 Образец
Рис. 1 Образец

Реализация

Preprocessing

Для начала, нужно узнать диапазон случайных чисел, где мы будем рисовать линию(индивид). Для этого, построил гистограмму картинки(рис. 2. По сумме цветов каждого пикселя, например: если строка полностью белая, то сумма пикселей будет равна 255) по высоте картинки. Чтобы было удобно, можно сделать инверсию, тогда белый цвет будет равен нулю.

Рис. 2
Рис. 2

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

Рис. 3
Рис. 3

Если рисовать линии по максимальным(синяя) и минимальным(зеленая) точкам по этой гистограмме, то получится нижняя картинка(рис. 4)

Рис. 4
Рис. 4

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

Генетический алгоритм

Для начала, создадим интерфейс нашего алгоритма, так мы можем использовать свойство полиморфизм:

from abc import abstractmethod, abstractproperty


class GeneticAlgorithm():
    """Genetic Algorithm Interface."""

    @abstractmethod
    def create_population(self):
        pass

    @abstractmethod
    def selection(self):
        pass

    @abstractmethod
    def mutation(self):
        pass

    @abstractmethod
    def cross(self):
        pass


    @abstractmethod
    def call(self):
        pass

Интерфейс состоит из таких функций:

  • create_population – создание начальной популяций;

  • selection – алгоритм отбора;

  • mutation – алгоритм мутации;

  • cross – алгоритм скрещивания;

  • call – функция, которая вызывает предедущие 3 функций;

Прежде чем приступать к реализаций алгоритма, нам нужно создать индивида. Индивид объявлен следующим образом:

import numpy as np
import random

class Individ:
    """Generate a new individ."""
    
    def __init__(self, y1, y2, length):   
        self.length = length   
        self.A=np.random.randint(y1, y2, self.length)    # Declare the attribute "A" of our individ (this will be the line 010..101).
        self.fit=0                                       # Declare the attribute "fit" of the individ (this will be the sum of the elements of our line 010..101) (for now, we will assign it the value 0)
    

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

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

class SimpleSegmentationGA(GeneticAlgorithm):
    """Genetic Algorithm Implementation."""

    def __init__(self, pop_num, lenght, delta_x, gray):
        self.pop_num = pop_num
        self.lenght = lenght    # Length of individ.
        self.delta_x =  delta_x # Value of h.
        self.gray = 256 - gray # Inversion.

Функция create_population описывает создание начальной популяции.

def create_population(self, y1, y2):
  """Creates a population, Dad, Mom and 4 sons"""

  self.y1 = y1
  self.y2 = y2
  self.population = []                                               # Declare an array "population" in which we will store a population of 5 individuals.
  for i in range(self.pop_num):           
    c=Individ(self.y1, self.y2, self.lenght)                       # Create a new individual.
    self.population.append(c)                                      # Add the i-th unique individual to the array (fill in our population)


    self.mother = Individ(self.y1, self.y2, self.lenght)               # Initialize the variables with which we will work: mom, dad, 4 sons ..
    self.father = Individ(self.y1, self.y2, self.lenght)                     
    self.son1 = Individ(self.y1, self.y2, self.lenght)                       
    self.son2 = Individ(self.y1, self.y2, self.lenght)
    self.son3 = Individ(self.y1, self.y2, self.lenght)
    self.son4 = Individ(self.y1, self.y2, self.lenght)
    self.par_and_sons = []                                             #.. and an array of individs "Parents and Children" in which we will store

    for j in range(self.pop_num*3):                                    # Initialize our array of "Parents and Sons" with random individs.
      self.par_and_sons.append(Individ(self.y1, self.y2, self.lenght))

Функция create_population создает родителей, а также 4 сыновей.

После того, как были сформированы «семьи» из особей, для скрещивания, нужно скрестить их хромосомы, чтобы получить детей с новыми хромосомами. Функция cross описывает скрещивание следующим образом:

def cross(self):
  """Crosses the best individs with each other."""

  for i in range(self.pop_num):                                      # Put in the first pop_num elements of the "Parents and Sons" array our entire input population.
    self.par_and_sons[i].A=self.population[i].A.copy()

    random.shuffle(self.population)                                    # Shuffle population.

    tt=0                                                               # The counter that is needed to implement a non-trivial crossing.
    for s in range(0,self.pop_num,2):                                  # From 0 to pop_num with step 2. That is. here we take pop_num / 2 pairs of parents.
      self.mother.A=self.population[tt+int(self.pop_num/2)].A        # Let the last pop_num / 2 individuals of our population be our mothers.
      self.father.A=self.population[tt].A                            # And let first pop_num / 2 individuals of our population be dads.

      tt=tt+1    
      ran=random.random()

      for n in range(self.lenght):                                   # Crossover.
        if random.random()>0.5:
          self.son1.A[n] = self.father.A[n]
          self.son2.A[self.lenght-1-n] = self.father.A[n]
          self.son3.A[n] = self.mother.A[n]
          self.son4.A[self.lenght-1-n] = self.mother.A[n]
        else:
          self.son1.A[n] = self.mother.A[n]
          self.son2.A[self.lenght-1-n] = self.mother.A[n]
          self.son3.A[n] = self.father.A[n]
          self.son4.A[self.lenght-1-n] = self.father.A[n]

        self.par_and_sons[self.pop_num+2*s].A = self.son1.A.copy()
        self.par_and_sons[self.pop_num+2*s+1].A = self.son2.A.copy()
        self.par_and_sons[self.pop_num+2*s+2].A = self.son3.A.copy()
        self.par_and_sons[self.pop_num+2*s+3].A = self.son4.A.copy()

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

def mutation(self):
  """Mutates individuals with a 20% probability."""

  for r in range(self.pop_num*3, 5):                                 # Mutation.
    for w in range(0,self.lenght):              
      if random.random()<0.2:                  
        self.par_and_sons[r].A[w] = self.par_and_sons[r].A[w] + np.random.randint(-20, 20)  # Offset + -20 pixels.

Метод mutation должен изменить хромосому, которая поступает к нему. Как правило, устанавливают небольшую вероятность мутации, например, единицы процентов, чтобы все-таки сохранялись хромосомы, полученные на основе родителей и таким образом улучшали популяцию.

После скрещивания и мутации обычно наступает этап отбора, на котором уничтожаются самые неудачные особи. Для этого используется метод selection, который объявлен следующим образом:

def selection(self):
  """Sorts by fit and selects the best pop_num individs."""

  for i in range(self.pop_num*3):                                    # It is important. Next, we will rank the array of parents and children in ascending order of survivability (sum (fit)).
    self.par_and_sons[i].fit = SimpleSegmentationGA.fitness_function(self.gray, self.delta_x, self.lenght, self.par_and_sons[i].A)

    #  Sort.
    self.par_and_sons = sorted(self.par_and_sons, key=lambda individ: individ.fit)   
    self.population=self.par_and_sons[:self.pop_num].copy()

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

Фитнес функция объявлен следующим образом:

def fitness(image, delta_x, length, individ):                      
    """Responsible for calculating the "fit" (counts the amount)."""
    
    summa = 0
    sum_vrt = 0
    for i in range(length):                 
        sum_ = np.sum(image[individ[i], i*delta_x:i*delta_x+delta_x])
        if i>0:
            if individ[i]>individ[i-1]:
                sum_vrt = np.sum(image[individ[i-1]:individ[i], i*delta_x])
            else:
                sum_vrt = np.sum(image[individ[i]:individ[i-1], i*delta_x])
        summa=summa + sum_ + sum_vrt       
    return summa

В этой функций мы учитываем сумму горизонтальных, а также соединяющих линии. У нас белый цвет имеет вес 1, а черный 256.

Последний метод call который вызывает три других метода объявлен следующим образом:

def call(self):
  """Calls other functions and returns the selected population."""

  self.cross()
  self.mutation()
  self.selection()

  return  self.population[0]

Метод call должен возвращать отобранную популяцию.

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

import numpy as np
import random, time
import cv2 
from scipy.ndimage import gaussian_filter
from scipy.signal import find_peaks
from numba import njit
import pymp

@njit
def fitness(image, delta_x, length, individ):                      
    """Responsible for calculating the "fit" (counts the amount)."""
    
    summa = 0
    sum_vrt = 0
    for i in range(length):                 
        sum_ = np.sum(image[individ[i], i*delta_x:i*delta_x+delta_x])
        if i>0:
            if individ[i]>individ[i-1]:
                sum_vrt = np.sum(image[individ[i-1]:individ[i], i*delta_x])
            else:
                sum_vrt = np.sum(image[individ[i]:individ[i-1], i*delta_x])
        summa=summa + sum_ + sum_vrt       
    return summa


def find_peaks_(image):
    """Calculates ranges of random numbers for our individs."""

    height, width = image.shape[:2]
    img_matrix = [sum(i)/len(i) for i in image]
    x=[i for i in range(height)]
    y = [255-i for i in img_matrix]
    y = gaussian_filter(y, sigma=20)
    maxs, _ = find_peaks(y)
    maxs = maxs.tolist()

    return maxs

def run(gaObj, peaks, epoch, parallel=True, number_cpu=4):
    """Can choose how to run."""
   
    gen_lines = pymp.shared.list()
    if parallel:
        with pymp.Parallel(number_cpu) as p:
            range_peaks = p.range(len(peaks)-1)
            gen_lines = run_genetic_algorithm(gaObj, peaks, epoch, range_peaks, gen_lines)
    else:
        range_peaks = range(len(peaks)-1)
        gen_lines = run_genetic_algorithm(gaObj, peaks, epoch, range_peaks, gen_lines)
              
    return np.moveaxis(np.array(gen_lines), 0, 1)    # Swap line and epoch axes.


def draw_lines(image, lines, delta_x, imagename, epoch="last", color=(0,0,255), thickness = 3, IMG_FOLDER='output'):
    """Draws the result of a genetic algorithm."""
    
    image_copy = image.copy()
    for j in lines:
        for i in range(len(j)):
            x1 = i*delta_x
            x2 = i*delta_x+delta_x
            y1 = j[i]
            y2 = j[i]
            start_point = (x1, y1)

            if i>0:
                cv2.line(image_copy, preview_point, start_point, color, thickness)
            end_point = (x2, y2)

            cv2.line(image_copy, start_point, end_point, color, thickness)
            preview_point = end_point
    cv2.imwrite(f"{IMG_FOLDER}/{imagename[:-4]}_gen_line_{epoch}.jpg", image_copy)


def run_genetic_algorithm(gaObj, peaks, epoch, range_peaks, gen_lines):
    """Runs a genetic alghoritm."""

    for line in range_peaks:
        gaObj.create_population(peaks[line], peaks[line+1])
        epoch_line = pymp.shared.list()
        for p in range(epoch):  
            st_time = time.time()                  
            gen_line = gaObj.call()
            epoch_line.append(gen_line.A)            # For draw results each epoch, add results of each epoch.
            print(f'Line = {line}, Epoch = {p}, fit = {gen_line.fit}, Time = {time.time()-st_time}') 
        gen_lines.append(epoch_line)
    
    return gen_lines

def crop_lines(image, lines, delta_x, imagename, IMG_FOLDER='crops'):
    """Crop the lines."""

    for i in range(-1,len(lines)):
        height, width = image.shape[:2]

        if i == (-1):
            first_line = [[i*delta_x, 0] for i, el in enumerate(lines[i])]
        else:
            first_line = [[i*delta_x, el] for i, el in enumerate(lines[i])]

        first_line = first_line[::-1] # Reverse first line.
        
        if i < len(lines)-1:
            second_line = [[i*delta_x, el] for i, el in enumerate(lines[i+1])]
        else:
            second_line = [[i*delta_x, height] for i, el in enumerate(lines[i])]

        points = np.array([first_line + second_line])
        mask = np.zeros((height, width), dtype=np.uint8)
        cv2.fillPoly(mask, points, (255))

        res = cv2.bitwise_and(image,image,mask = mask)

        rect = cv2.boundingRect(points) # Returns (x,y,w,h) of the rect
        im2 = np.full((res.shape[0], res.shape[1], 3), (0, 255, 0), dtype=np.uint8 ) # You can also use other colors or simply load another image of the same size
        maskInv = cv2.bitwise_not(mask)
        colorCrop = cv2.bitwise_or(im2,im2,mask = maskInv)
        finalIm = res + colorCrop
        cropped = finalIm[rect[1]: rect[1] + rect[3], rect[0]: rect[0] + rect[2]]

        cv2.imwrite(f"{IMG_FOLDER}/croped_{imagename[:-4]}_{i}.png", cropped)

Так как, генетический алгоритм является итерационной задачей, он занимает много времени, основное время занимает расчет фитнес функций. Чтобы увеличить время обработки мы использовали библиотеку numba для фитнес функций и уменшили скорость обработки в 27 раз(190sec VS 7sec для одного изображения). Также использовали библиотеку pymp для  распараллеливания, итого время сократилась до 3,5 сек. на одно изображение.

Запускаемый файл объявлен следующим образом:

import cv2 
import glob, os
from utils import *
from SimpleSegmentationGA import SimpleSegmentationGA



if __name__ == '__main__':

    # Hyper parameters for genetic alghoritms.
    POP_NUM=80
    DELTAX=50 # Value of h.
    EPOCH=100
    IMAGES_PATH = 'input'
    # IMAGE_PATH = '7.jpg'
    

    images = glob.glob(f'{IMAGES_PATH}/*.jpg')
    for imagename in images:
        fstart_time = time.time()
        # Image operations. 
        image = cv2.imread(imagename)
        height, width = image.shape[:2]
        gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

        # Calculate individ's lenght.
        length_individ = int(width/DELTAX)

        # Calculate the range of random numbers for an individ.
        peaks = find_peaks_(gray) 
        
        # Create object of class.
        ssga = SimpleSegmentationGA(POP_NUM, length_individ, DELTAX, gray)

        start_time = time.time()
        # Run genetic algorithm.
        lines = run(ssga, peaks, EPOCH, parallel=True)
        print('Time run =', time.time()-start_time)

        last_epoch_lines = sorted(lines[-1], key = lambda x:x[0]) # Sort for crop. Because when using parallel, the lines lose consistency.

        start_time = time.time()
        # Draw the result of the genetic alghoritm. lines[-1] -> result of last epoch.
        draw_lines(image, last_epoch_lines, DELTAX, os.path.basename(imagename))
        print('Time draw_lines=", time.time()-start_time)

        start_time = time.time()
        # Crop the result of genetic alghoritm.
        crop_lines(image, last_epoch_lines, DELTAX, os.path.basename(imagename))
        print("Time crop_lines=", time.time()-start_time)
        print("Time for one image=", time.time()-fstart_time)
        

Результат оправдал ожидание:

Рис. 5
Рис. 5

Исходный код можете найти здесь.


Source link

Total
0
Shares
Previous Post

Product analyst (Marketing)

Next Post
Мошенники «приручили» боты в Telegram для шантажа пользователей

Мошенники «приручили» боты в Telegram для шантажа пользователей

Related Posts