Приведу наиболее интересные отрывки из моей переписки с Tulon'ом (автором Scan Tailor) относительно деворпинга:
Можно ли сделать консольную версию СТ-деворпинга?
Сделать-то можно, только не будет оно хорошо работать. Причина в том, что нет хорошего алгоритма нахождения вертикальных границ контента. Существующий алгоритм предполагает, что весь мусор уже был обрезан рамкой контента.
Как перенести в консольную версию синюю сетку?
Сетка переносится без особых проблем. Берется неискженная сетка
и искажается с помощью объекта DewarpingPointMapper. Для его построения нужна DistortionModel - это верхняя и нижняя кривая плюс две линии - левая и
правая граница контента.
С чего начать перенос в консольную версию?
Советую начать как раз с определения вертикальных границ (DetectVertContentBounds.cpp). Все остальное зависит он него. Потом продвигайтесь в сторону трассировки строк текста (TextLineTracer.cpp, TextLineRefiner.cpp, TopBottomLineTracer.cpp).
Красные точки ведут себя ужасно капризно.
Со сплайнами всегда так. На любую синюю точку влияют аж 4 соседние красные точки. По-другому никак - сплайну нужно поддерживать одинаковость первых двух производных на границах сегментов.
Синяя сетка - это всего лишь сэмплинг модели искажения. Захочется больше узлов - просто измените константу.
Можно вообще отказаться от сплайнов и работать с ломанными (polylines). Понятно, что в этом случае узлов нужно будет гораздо больше.
Во многих статьях строки текста аппроксимируются линейно-квадратичным сплайном вида y = ax*x + bx + c.
Это весьма простая модель, которая не справится с сильным изгибом.
У Вас по какой схеме всё работает?
Я не использую квадратичные сплайны. В моей схеме:
1. Делается грубое обнаружение строк. Получаем polyline. О плавности на
этом этапе речь не идет.
2. С помощью сдвоенных змей (coupled snakes) улучшаем наш polyline.
3. Подгоняем (fitting) X-spline произвольной сложности, даже не столько ради
дополнительной плавности (хотя это тоже), сколько для возможности ручной правки.
4. Выбираем пару лучших сплайнов (чем они дальше друг от друга, тем
лучше), а остальные отбрасываем.
В общем, если бы не ручное редактирование, сплайнов у меня совсем бы не было.
Змеи дают вполне достаточную гладкость. Идею со змеями я позаимствовал
отсюда:
http://iupr1.cs.uni-kl.de/~shared/publications/2009-bukhari-cbdar-dewarping-document-image.pdf
Общую модель искажений - отсюда:
http://pdf.aminer.org/000/292/904/a_cylindrical_surface_model_to_rectify_the_bound_document_image.pdf
От себя добавил коррекцию перспективы (homographic transform).
Вы говорили, что сложно определить вертикальную границу текста. А как же линия сопряжения двух соседних страниц книги?
Ее можно использовать, если в качестве кривых брать не линии текста,
а верхнюю и нижнюю границы страницы. Я их кстати ищу в TopBottomLineTracer.cpp, но их может и не быть на скане. Строки текста сильно не доходят до этой линии, так что я не пытался искать и использовать именно эту линию. Так или иначе, с противоположной границей все еще сложнее.
Кстати - сплошные чёрные полосы должны очень часто попадать на сырые сканы.
Как я уже сказал выше, я их тоже использую, если TopBottomLineTracer их находит.
Насколько я понимаю, всё, что мне нужно - это просто программно поработать нужным образом с объектом distortion_model внутри OutputGenerator::processWithDewarping ?
Для начала нужно откуда-то получить параметры модели, а именно две
кривые (просто набор точек - polyline) и параметр depth perception.
Предполагается, что если соединить первые точки этих двух кривых, получим левую вертикальную границу контента. Если последние точки - тогда правую.
Вопрос только в том - а как с ним работать программно?
Строго говоря DistortionModel вам не обязательно использовать. Он
существует главным образом для сохранения / загрузки из проекта, а также для проверки равенства моделей. Математика деварпинга находится в классе
CylindricalSurfaceDewarper, который параметризуется не DistortionModel, а отдельными его элементами.
Или же, может быть, надо не с красными точками работать - а, скажем, напрямую с узлами сетки? Вот я вижу в классе DistortionModel есть свойство Curve m_topCurve - значит, надо, видимо, программно переопределить как-то m_topCurve - чтобы сетка выше задралась?
Curve - это что-то типа union { Spline; Polyline }. Есть Spline - хорошо. Нет Spline - сойдет и Polyline. Опять-же, Curve существует главным образом для сохранения в проект и для проверки одинаковости.
CylindricalSurfaceDewarper принимает не XSpline и не Curve, а просто std::vector<QPointF>.
m_topSpline.spline() возвращает некий класс XSpline - кстати, я так и не
понял - а что же такое X-spline?
X-spline достаточно новый сплайн - в 90х его по моему придумали. Используют в основном в видео-редакторах для интерполяции выделения между ключевыми кадрами. Я про него только потому и знаю, что на работе мы как раз пишем видеоредактор.
А вообще он гораздо мощнее B-spline'а по многим параметрам.
Мне с чем работать - с m_xspline или с m_polyline (чтобы двигать красные точки)?
Красные точки - это контрольные точки XSpline, но програмно я бы стал
работать с Polyline, поскольку там все ясно и предсказуемо. Повторю, что если бы не необходимость визуального редактирования, никаких сплайнов я бы вообще делать не стал. Сплайн все равно в конечном итоге конвертируется
(сэмплируется) в polyline (то есть в просто набор точек).
А что такое controlPointTension - что значит "Tension"?
А это как раз то, что делает X-Spline мощнее B-Spline. Если tension <= 0,
то кривая будет проходить через данную контрольную точку. То есть красная
точка будет на синей кривой. Чем ближе tension к -1, тем более сглаженным будет проход.
При tension = 0 проход будет совсем угловатым, как в многоугольнике.
При tension > 0 кривая уже не будет проходить через контрольную точку, но
будет как бы притягиваться к ней пружиной. Чем ближе tension к единице, тем
слабее пружина. Те XSpline, которые внутри Curve - у них у крайних точек tension 0, а у остальных 1. Почему не -1? Работать бы работало, но нужно было бы больше контрольных точек для достижения нужного эффекта. Опять же, вам класс Curve не особенно нужен, так что вам никто не мешает заиметь свой XSpline со своими параметрами. А можно и вовсе без него обойтись.
Ещё мне нужно - где задаётся шаг синей сетки, другими словами, как-то бы узнать расстояния между и позиции синих узлов сетки, чтобы выставить свои красные точки точно в них.
Синяя сетка - понятие чисто эфемерное. Есть модель, которая может варпить или деварпить любую точку. Мы ей говорим - вот тебе матрица 30x30 точек в виде неискаженной решетки. Искази каждую из этих точек, а мы это потом нарисуем поверх изображения, соединяя точки (для простоты) прямыми линиями.
Размеры матрицы задаются в файле DewarpingView.cpp:
int const num_vert_grid_lines = 30;
int const num_hor_grid_lines = 30;
Красные точки так просто вверх не поднимешь - а они друг с другом взаимосвязаны формулой сплайна (X-сплайна?)
Не парьтесь со сплайнами - они для людей, а не для программ. Генерируйте простой polyline в виде набора точек.
Так всё-таки с чем именно мне работать - с DistortionModel или с
CylindricalSurfaceDewarper?
От CylindricalSurfaceDewarper вы все равно никуда не убежите, а вот
DistortionModel не особенно нужна, если переносить dewarping
в консольную программу.
Я бы рекомендовал сразу выкидывать XSpline из объекта Curve, и впоследствии работать только с polyline. То есть когда закончите строить свою DistortionModel, XSpline'а в ней не будет вообще - только polyline.
Кстати прилично работающий алгоритм для подгонки сплайнов был изобретен только в 2002 году, а мне пришлось серьезно подучить матанализ, чтобы его
реализовать.
Так или иначе, вы сделали как я советовал - забить на XSpline и работать
только с polyline.
Так что же это получается - выходит, что красные точки добавляются только на XSpline - а на polyline их не добавишь? Значит, мне недостаточно работы с одной только полилинией - придётся оперировать ещё и х-сплайном?
Только если вас чем-то не устраивает авто-подогнанный сплайн.
Кстати, а как Ваш автоматический деворпинг - добавляет ли он вообще хоть когда-нибудь красные точки? Умеет ли он это делать, и где и как он это делает?
Там происходит ровно то же самое, что и у вас - автоподгонка сплайна.
Количество контрольных точек этого сплайна зашито в код:
int const initial_spline_points = 5;
в DistortionModelBuilder.cpp
Есть ещё старый исходный код Dewarping от Rob с форума diybookscanner.org. Скажите - деворпинг в Скан Тейлоре - это его потомок или нет? Другими словами, есть ли мне смысл переносить Dewarping от Rob в консольное приложение - или сразу деворпинг из Скан Тейлора туда перенести? Какова взаимосвязь между этими 2-мя деворпингами?
Деварпинг от Rob'а больше похож на деварпинг от Leptonica, чем на тот,
что в Scan Tailor'е. И у Rob'а (точно) и в Leptonica (не уверен, но догадываюсь),
если хоть одна линия текста была плохо протрассирована, результат будет паршивым.
В ST есть неплохая вероятность, что эта плохая линия не будет выбрана в качестве одной из двух репрезентативных. Еще у Rob'а гораздо более сложная
математическая модель сплайна. Если в Leptonica это просто сегмент параболы, то у Rob'а - сложная нелинейная функция, в которой есть и степени, и синус, и чего там только нет.
В результате приходится использовать сложный алгоритм нелинейной
оптимизации Levenberg-Marquard, который весьма неторопливо работает, и не гарантирует (как и другие алгоритмы) нахождения глобального оптимума.
Кстати, а как Ваш автоматический деворпинг - добавляет ли он вообще хоть когда-нибудь красные точки? Умеет ли он это делать, и где и как он это делает?
Не добавляет. Процедура подгонки сплайна работает так:
Создается сплайн в виде прямой линии, начинающийся и заканчивающийся там же, где и polyline. Количество контрольных точек (тех самых, которые красные)
и соответствующие им значения tension выбираются заранее. Начальное
положение контрольных точек - равномерно по прямой. Про значения tension я уже писал.
Затем алгоритм подгонки начинает двигать существующие контрольные точки,
чтобы приблизить форму сплайна к форме polyline.
А количество узлов полилинии и количество контрольных точек сплайна (красных точек) обязано совпадать?
Нет. В этом весь смысл. Чем больше точек в polyline, тем лучше, но это
будет невозможно редактировать вручную. Поэтому к polyline подгоняется сплайн, у которого всего несколько контрольных точек. После ручного редактирования сплайна, он конвертируется (сэмплируется) обратно в polyline.
Что будет, если оставить на сплайне только 2 красные точки - начальную и конечную?
Сплайн с двумя контрольными точками не будет иметь кривизны - это просто отрезок прямой. Насколько я помню - initNewSpline используется только для ручного редактирования результата авто-деварпинга. Авто-деварпинг все равно будет генерировать сплайны с 5 контрольными точками. Число 5 выбрано
потому, что 4 не хватало при сильном искривлении. А в общем - чем меньше, тем лучше.
Я хотел сконвертировать каждый добавленный мною узел полилинии в красную точку.
Существующий механизм автоподгонки сплайнов все сделает за вас. Просто конструируйте Curve на основе polyline, а когда дело дойдет до ручного
редактирования, к ней будет подогнан сплайн.
Каково соотношение между ними? Т.е. между узлами полилинии и красными точками? Обязателен ли порядок следования точек внутри полилинии - или важны лишь координаты? Т.е. если я хочу добавить среднюю точку между концами (как полилинии, так и х-сплайна) - мне надо сделать insert, а просто push_back не подойдёт?
У polyline - чем больше точек, тем лучше (потомучто будет лучше качество деварпинга, но производительность может пострадать), а у spline - чем меньше, тем лучше, потому-что будет проще редактировать вручную. Для polyline push_back подойдет. У XSpline свой API.
Как бы то ни было - всё равно после выставления полилинии, мне нужно соответствующим образом выставить красные точки. Практически вопрос стоит о том, как и где их добавлять (убирать тоже, наверно).
Алгоритм автоподгонки все сделает за вас (кроме определения оптимального количества красных точек).
Потом я ещё спрошу - какова математическая зависимость между узлами полилинии, и обязан ли я её соблюсти после выставления точек полилинии по краю книги.
Никакой, но неявно подразумевается плавность изгибов, а то деварпинг
получится угловатый.
В этом и есть суть моего вопроса - как и где грамотно сформировать distortion_model на основании расставленных красных точек, чтобы скан начал реально деворпиться по моей синей сетке?
DistortionModel - это всего-лишь пара объектов Curve. Объект Curve можно построить из XSpline. Ну а XSpline можно построить путем планомерного
добавления контрольных точек. Но осторожнее с параметром tension у контрольных точек - при загрузке проекта делается предположение, что у крайних точек tension будет 0, а у остальных 1. Но tension равный 1, это approximating режим, а в этом режиме контрольные точки будут не на сплайне! То есть то, что вы пытаетесь сделать, работать не будет. Вот если
в Curve::deserializeXSpline() поменять tension с 1 на -1, тогда может и будет, если в других местах нет подобных предположений.
Всё же с полилинией не следует работать, а работать надо всё-таки непосредственно с красными точками - так точней.
Красные точки и не должны быть на линии, при этом сплайн, порожденный ими - будет. Сплайн, контрольные точки которого всегда находятся на самом сплайне называется interpolating spline. У которого не находятся - approximating spline. X-spline может работать в обоих режимах, чего кстати не умеет ни один другой сплайн. Более того, можно часть контрольных
точек сделать interpolating, а другую часть approximating. Контролируется это параметром tension, про который я уже писал. Так вот, СТ конфигурирует две
крайние контрольные (красные) точки как interpolating, а остальные - как
approximating. Мог бы я все точки сделать interpolating? Мог, но тогда 5ти
не хватило бы для сильных искривлений, так что пришлось бы делать 6 или 7.
Думаю, надо теперь как-то попытаться заняться улучшением Вашего автоматического деворпинга. У Вас есть какие-нибудь идеи?
Надо улучшать определение вертикальных границ, при этом не используя рамку
контента. Это позволит в будущем перенести деварпинг на стадию Deskew.
Сложных случаев два класса:
1. Мало строк текста или строки не выровнены по правому краю.
2. Строк хватает, но есть контент, вылезающий за логическую вертикальную
границу.
Тот алгоритм, который сейчас в основной ветке ST, может справиться с
первым случаем (но правда использует рамку контента для очистки мусора по
краям). Для второго класса можно использовать преобразование Хафа, но
такого алгоритма, который работал бы в обоих случаях мне пока придумать не
удалось.
Надо сказать, что ни в одной из статей по деварпингу не уделяется должного внимания определению вертикальных границ. Буквально пару предложений этому посвящают, а все примеры в статьях представляют из себя простые случаи.
А почему нельзя принять вертикальные границы просто вертикальными?
Во-первых, они не всегда вертикальные, даже не всегда параллельные. Во-вторых, даже когда они вертикальные, всё равно нужно решать, на какие именно x-координаты их поместить. Будут слишком далеко отстоять от строк текста - сплайн будет норовить сделать изгиб, чтобы достать до вертикальной границы наиболее коротким путем. Будут пересекать контент - отрезанные части вообще не будут распрямляться.
Ваш автоматический деворпинг не замечает малых искривлений концов строки.
С концами строк тяжело, особенно с левыми концами, когда там заглавная буква, да еще красная строка - начало абзаца. Тем не менее, нет такого требования, чтобы все строки хорошо трассировались. Пары хорошо оттрассированных строк будет вполне достаточно, если они на приличном расстоянии друг от друга. Ну а с верхними / нижними гранями вообще такой проблемы нет, так как грань присутствует по обе стороны от вертикальной границы.
Как можно улучшить детектирование?
В двух словах - сначала сдвоенные змеи, притягивающиеся к размытому вертикальному компоненту градиента (хорошо видно в дебаг режиме), а затем
подгонка сплайна.
Кстати я вспомнил еще одну причину, по которой я делаю подгонку сплайнов -
она у меня также выполняет роль наращивания кривой, чтобы достать до
вертикальной границы.
Мне нужно изображение с вкладки Dewarping стадии Output - хотя бы внутри Task.
Изображение, которое передается в DewarpingView - это самое что ни на есть оригинальное изображение страницы (или разворота) прочитанное с диска.
Оно передается в Task::process() как часть объекта FilterData.
Уже при отрисовке оно обрубается по краям (в зависимости от режима разреза)
и вращается на нужный угол. DistortionModel однако задан именно в координатах исходного, неповернутого и необрезанного изображения, так что обрезать вам его никакого смысла нет, разве-что повернуть на 90 градусов при
необходимости, чисто для удобства.
