Обнаружение «реки» в тексте

175

В рамках обмена стеками TeX мы обсуждали, как обнаружить «реки» в параграфах этого вопроса .

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

введите описание изображения здесь

Существует заинтересованность в автоматическом обнаружении этих рек, чтобы их можно было избежать (возможно, путем ручного редактирования текста). Raphink добивается некоторого прогресса на уровне TeX (который знает только положения глифов и ограничивающие рамки), но я уверен, что лучший способ обнаружить реки - это некоторая обработка изображений (поскольку формы глифов очень важны и недоступны для TeX) , Я пробовал различные способы извлечения рек из приведенного выше изображения, но моя простая идея применения небольшого количества эллипсоидального размытия не кажется достаточно хорошей. Я также попробовал немного РадонаХоть фильтрация на основе преобразования, но я тоже никуда не попал. Реки очень хорошо видны для схем обнаружения признаков человеческого глаза / сетчатки / мозга, и я думаю, что это может быть преобразовано в какую-то операцию фильтрации, но я не могу заставить ее работать. Есть идеи?

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

РЕДАКТИРОВАТЬ: endolith спросил, почему я придерживаюсь подхода, основанного на обработке изображений, учитывая, что в TeX у нас есть доступ к позициям глифов, промежуткам и т. Д., И может быть намного быстрее и надежнее использовать алгоритм, который проверяет фактический текст. Моя причина сделать что-то другое, потому что формаиз глифов может повлиять на то, насколько заметна река, и на уровне текста очень трудно рассмотреть эту форму (которая зависит от шрифта, лигатуры и т. д.). Для примера того, как форма глифов может быть важна, рассмотрим следующие два примера, где различие между ними состоит в том, что я заменил несколько глифов на другие почти такой же ширины, чтобы анализ на основе текста мог рассмотреть их одинаково хорошо / плохо. Обратите внимание, однако, что реки в первом примере намного хуже, чем во втором.

введите описание изображения здесь

введите описание изображения здесь

Лев Бишоп
источник
5
+1 Мне нравится этот вопрос. Моя первая мысль - преобразование Хафа , но, вероятно, потребуется предварительная обработка. Может быть, сначала фильтр дилатации .
Datageist
Я удивлен, что преобразование Радона не сработало. Как ты сделал это?
эндолит
@endolith: Ничего сложного. Я использовал ImageLines[]от Mathematica, с и без предварительной обработки. Я предполагаю, что это технически использует преобразование Хафа, а не Радона. Я не удивлюсь, если правильная предварительная обработка (я не пробовал предложенный datageist фильтр расширения) и / или настройки параметров могут сделать эту работу.
Лев Епископ
Google Image Search для рек также показывает "извилистые" реки. Вы хотите найти их? cdn.ilovetypography.com/img/text-river1.gif
эндолиты
@endolith Я думаю, что в конечном итоге я хочу повторить обработку визуальной системы человека, которая отвлекает определенные конфигурации пространства. Так как это может случиться и с извилистыми реками, я бы хотел их поймать, хотя прямые, похоже, в большей степени являются проблемой. Еще лучше было бы определить количество «плохих» рек таким образом, чтобы они соответствовали тому, насколько сильно они видны при чтении текста. Но это все очень субъективно и трудно измерить. Во-первых, подойдет просто ловля действительно всех плохих рек без слишком большого количества ложных срабатываний.
Лев Епископ

Ответы:

135

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

(1) Откройте изображение с маской nPix-by-1, где nPix - это вертикальное расстояние между буквами.

#% read image
img = rgb2gray('http://i.stack.imgur.com/4ShOW.png');

%# threshold and open with a rectangle
%# that is roughly letter sized
bwImg = img > 200; %# threshold of 200 is better than 128

opImg = imopen(bwImg,ones(13,1));

введите описание изображения здесь

(2) Откройте изображение с маской 1 × mPix, чтобы исключить то, что слишком узкое, чтобы быть рекой.

opImg = imopen(opImg,ones(1,5));

введите описание изображения здесь

(3) Удалите горизонтальные «реки и озера» из-за пробелов между абзацами или отступов. Для этого мы удаляем все строки, которые являются истинными, и открываем их с помощью маски nPix-by-1, которая, как мы знаем, не повлияет на реки, которые мы нашли ранее.

Чтобы удалить озера, мы можем использовать открывающую маску, которая немного больше, чем nPix-by-nPix.

На этом этапе мы также можем выбросить все, что слишком мало, чтобы быть настоящей рекой, то есть все, что охватывает меньшую площадь, чем (nPix + 2) * (mPix + 2) * 4 (что даст нам ~ 3 строки). +2 есть, потому что мы знаем, что все объекты имеют как минимум nPix по высоте и mPix по ширине, и мы хотим пойти немного выше этого.

%# horizontal river: just look for rows that are all true
opImg(all(opImg,2),:) = false;
%# open with line spacing (nPix)
opImg = imopen(opImg,ones(13,1));

%# remove lakes with nPix+2
opImg = opImg & ~imopen(opImg,ones(15,15)); 

%# remove small fry
opImg = bwareaopen(opImg,7*15*4);

введите описание изображения здесь

(4) Если нас интересует не только длина, но и ширина реки, мы можем объединить преобразование расстояния со скелетом.

   dt = bwdist(~opImg);
   sk = bwmorph(opImg,'skel',inf);
   %# prune the skeleton a bit to remove branches
   sk = bwmorph(sk,'spur',7);

   riversWithWidth = dt.*sk;

введите описание изображения здесь (цвета соответствуют ширине реки (хотя цветовая полоса отключена в 2 раза)

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


Вот точно такой же анализ, примененный ко второму изображению «без реки»:

введите описание изображения здесь

Jonas
источник
Благодарю. У меня есть Matlab, поэтому я попробую это на некоторых других текстах, чтобы увидеть, насколько он будет надежным.
Лев Епископ
Интегрировать его обратно в TeX может быть другой проблемой, если только мы не сможем перенести это на Lua.
ℝaphink
@LevBishop: я думаю, что понимаю проблему немного лучше. Новое решение должно быть достаточно надежным.
Джонас
@levBishop: еще одно обновление.
Джонас
1
@LevBishop: только что заметил второе изображение. Оказывается, морфологический анализ делает свое дело.
Джонас
56

В Mathematica, используя эрозию и преобразование Хафа:

(*Get Your Images*)
i = Import /@ {"http://i.stack.imgur.com/4ShOW.png", 
               "http://i.stack.imgur.com/5UQwb.png"};

(*Erode and binarize*)
i1 = Binarize /@ (Erosion[#, 2] & /@ i);

(*Hough transform*)
lines = ImageLines[#, .5, "Segmented" -> True] & /@ i1;

(*Ready, show them*)
Show[#[[1]],Graphics[{Thick,Orange, Line /@ #[[2]]}]] & /@ Transpose[{i, lines}]

введите описание изображения здесь

Редактировать Отвечая на комментарий Мистера Волшебника

Если вы хотите избавиться от горизонтальных линий, просто сделайте что-то вроде этого (возможно, кто-то может сделать это проще):

Show[#[[1]], Graphics[{Thick, Orange, Line /@ #[[2]]}]] & /@ 
 Transpose[{i, Select[Flatten[#, 1], Chop@Last@(Subtract @@ #) != 0 &] & /@ lines}]

введите описание изображения здесь

Доктор белисарий
источник
1
Почему бы не избавиться от всех горизонтальных линий? (+1)
Мистер Волшебник
@Г-н. Просто чтобы показать, что все линии обнаруживаются ...
Доктор Белизариус
1
Это не является частью проблемы, не так ли?
Mr.Wizard
@Г-н. Отредактировано в соответствии с просьбой
д-р Белизариус
4
@belisarius Система координат, используемая в преобразовании Хафа, изменилась после 8.0.0, чтобы соответствовать системе преобразования Радона. Это в свою очередь изменило поведение ImageLines. В целом это улучшение, хотя в этом случае предпочтительнее предыдущее поведение. Если вы не хотите экспериментировать с пиковыми обнаружений, вы можете изменить соотношение сторон входного изображения , чтобы быть ближе к 1 и получить результат , аналогичный 8.0.0: lines = ImageLines[ImageResize[#, {300, 300}], .6, "Segmented" -> True] & /@ i1;. С учетом всего сказанного, для этой проблемы морфологический подход кажется более надежным.
Матиас Одисио
29

Хммм ... Я думаю, преобразование Радона не так просто извлечь из. (Преобразование Радона в основном вращает изображение, одновременно «просматривая его»). Это принцип, лежащий в основе CAT-сканирования.) Преобразование вашего изображения дает эту синограмму с «реками», образующими яркие пики, которые обведены кружком:

введите описание изображения здесь

Тот, что при повороте на 70 градусов, можно увидеть довольно отчетливо, как пик слева от этого графика среза по горизонтальной оси:

введите описание изображения здесь

Особенно, если текст был сначала размыт по Гауссу:

введите описание изображения здесь

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

Простая функция взвешивания косинуса хорошо работает на этом изображении:

введите описание изображения здесь

найти вертикальную реку под углом 90 градусов, которая является глобальными максимумами на синограмме:

введите описание изображения здесь

и на этом изображении обнаружение того, что под углом 104 градуса, хотя размытие сначала делает его более точным:

введите описание изображения здесь введите описание изображения здесь

( radon()Функция SciPy довольно тупая , или я бы отобразил этот пик обратно на исходное изображение в виде линии, проходящей через середину реки.)

Но он не находит ни одного из двух основных пиков в синограмме для вашего изображения после размытия и взвешивания:

введите описание изображения здесь

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

from pylab import *
from scipy.misc import radon
import Image

filename = 'rivers.png'
I = asarray(Image.open(filename).convert('L').rotate(90))

# Do the radon transform and display the result
a = radon(I, theta = mgrid[0:180])

# Remove offset
a = a - min(a.flat)

# Weight it to emphasize vertical lines
b = arange(shape(a)[1]) #
d = (0.5-0.5*cos(b*pi/90))*a

figure()
imshow(d.T)
gray()
show()

# Find the global maximum, plot it, print it
peak_x, peak_y = unravel_index(argmax(d),shape(d))
plot(peak_x, peak_y,'ro')
print len(d)- peak_x, 'pixels', peak_y, 'degrees'
эндолиты
источник
Что если бы вы сначала размыли с асимметричным гауссовым? То есть узкий в горизонтальном направлении, широкий в вертикальном направлении.
Джонас
@Jonas: Это, вероятно, поможет. Основная проблема заключается в автоматическом выделении пиков из фона, когда фон сильно меняется при вращении. Асимметричное размытие может сгладить горизонтальные полосы от линии к линии.
эндолит
Это хорошо работает для обнаружения вращения линий в тексте, по крайней мере: gist.github.com/endolith/334196bac1cac45a4893
эндолиты
16

Я обучил дискриминационный классификатор по пикселям, используя производные функции (до 2-го порядка) в разных масштабах.

Мои ярлыки:

этикетирование

Прогноз по тренировочному имиджу:

введите описание изображения здесь

Прогноз на двух других изображениях:

введите описание изображения здесь

введите описание изображения здесь

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

Бернхард Кауслер
источник
2

(Извините, этот пост не содержит удивительных демонстраций.)

Если вы хотите работать с информацией, которой уже располагает TeX (буквы и позиции), вы можете вручную классифицировать буквы и пары букв как «наклонные» в том или ином направлении. Например, «w» имеет угловые наклоны SW и SE, комбо «al» имеет угловой угол NW, «k» имеет угловой угол NE. (Не забывайте пунктуацию - кавычка, за которой следует буква, заполняющая нижнюю половину поля глифа, устанавливает хороший уклон; кавычка, за которой следует q, особенно сильна.)

Затем найдите вхождения соответствующих склонов на противоположных сторонах пространства - «w al» для реки SW-to-NE или «k T» для реки NW-SE. Когда вы найдете один на линии, посмотрите, происходит ли аналогичный, смещенный влево или вправо, на линии выше / ниже; когда вы найдете их, вероятно, есть река.

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

Вы можете стать немного более изощренным, измерив «силу» наклона: сколько передового бокса «пусто» из-за уклона и, таким образом, влияет на ширину реки. «w» довольно маленький, так как у него есть только маленький угол своего передового поля, чтобы внести свой вклад в ривер, но «V» очень сильный. «б» немного сильнее, чем «к»; более мягкая кривая дает более визуально непрерывный край реки, делая его более прочным и визуально более широким.

Xanthir
источник