Здарова, братишки! Хочу торгануть своей новой поделкой на PHP из области оптического распознования изображений. Этот скрипт позволяет определить угол наклона отсканированного документа и выровнять его.
Внутри я расскажу, как он работает, и выложу исходники.

Tagged with →  

28 Responses to Здарова, братишки!

  1. UpaFcuk:

    Принцип действия довольно прост, для реализации понадобился один класс и 200 строк кода:

    1. Изменяем изображение до разрешения в 40PPI (цифры пока не окончательные)

    2. Нормализуем изображение и переводим в двоичный двумерный массив.

    3. Перебираем угол наклона от -15 до +15 градусов, находя для каждого угла максимизированную производную по модулю от вертикального осевого спектра изображения.

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

    Специальный демо-скрипт украшает изображение спектрами для наглядности:

    Linux Nix Web Development - http://linuxoids.org/ размер 470x243, 65.81 kb

  2. UpaFcuk:

    Скачать исходник (v.0.1, ZIP, 900Кб). Требования: PHP5, не менее 128Мб ОЗУ для PHP, веб-сервер. Поддерживается и shell-режим.

    Linux Nix Web Development - http://linuxoids.org/ размер 499x283, 56.93 kb

  3. UpaFcuk:

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

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

  4. UpaFcuk:

    особые благодарности блогоюзеру Dobersoft за поддержку с мат.частью и эксперименты.

  5. D05Good:

    а по тестам узкое место где? ресайз?

  6. UpaFcuk:

    хорошая идея, бро.

    Загрузка картинки (545×678) 0.01 с.
    Ресэмплинг 150>40PPI 0.004 с.
    Нормализация и создание чб-массива 0.088 с.
    Поиск лучшего региона для нанализа (150x150px) 0.089 с.
    Триммирование массива 0.014 с.
    Подбор угла 1.818 c.
    Общее время 2.03 c.

    Думаю, надо переписать функцию поиска угла в сишку, плагином к PHP, или ещё как-то.
    Кто ни будь сталкивался?

  7. RetMega:

    Удачи со слипшимися буквами 😉

  8. RetMega:

    стоп стоп стоп, это просто поворот??? ) Тогда вопросов нет 🙂

  9. D05Good:

    как минимум ее надо оптимизировать, а потом, если никак, уже переписать

  10. D05Good:

    из того, что быстро просмотрел:
    — просчитай заранее таблицу sin и cos (шаг минимальный у тебя вроде есть, угол всегда не больше 45?)
    — оптимизируй проверки (например в самом центре $y>0 это всега true кроме старта цикла, так?)
    — pi() заранее присовить можно

    самый трэш — это прогон картинки (по y и х) для каждого шага угла.
    все переменные там есть кроме $x и $y, сократи формулу, все что болдом — можно же до обоих циклов подсчитать:

    $xR-$xR*$cos_a+$yR*$sin_a + $x*$cos_a — $y*$sin_a

    все равно, почти две секунды на прогон картинки — дофига, в функцию точно не оригинал картинки попадает?

  11. D05Good:

    array_sort — замерь тоже отдельно

  12. Tfomo:

    я изначально пошёл немного тупиковым путём — полным перебором параметров с поиском максимальной корреляции.

  13. UpaFcuk:

    Ну, при диапозоне 30°, шаге 3/8° (1/150рад.), массив 150х150 имеет 1.8 млн. итераций (80x150x150). Ранее удалось уменьшить кол-во итераций почти в три раза, делая предварительный проход с тройным шагом угла. Там, кстати, и выступает array_sort (два раза по 0.0003 сек).
    Да, 0.8с. из 1.8с. съедается вращением точки ($x0, $y0). Сейчас проверил, поиск в массиве 80х150х150 происходит за 0.1сек. Буду делать.
    «Холостые» циклы (80x150x150) занимают 0.12с на моём Core2Duo 2.4.

  14. UpaFcuk:

    Я бы, говно-кодер, хотел узнать, как в PHP сделать строку, например, 1.8 мб, и получать/записывать туда байт указывая его смещение. Массивы сильно расходуют память.

  15. Tfomo:

    это хороший вариант для Си, но не для PHP.

  16. D05Good:

    рнр для поворота картинок — не самый удачный выбор. попробуй расчитать угол поворота для начала на сервере, а сам поворот сделать через js+canvas в браузере, это апаратно делается и очень быстро (как минимум, это не будет валить сервер). хотя я не знаю причину выбора пхп как платформы для реализвации твоей идеи.

  17. Raewhite:

    есть готовая опенсорсная библиотека для распознавания — она прекрасно делает поворот документа

  18. KipaTa:

    Преобразование Хафа для линий — OpenCV
    Преобразование Хафа

    может быть имеет смысл воспользоваться готовыми методами, а не изобретать велосипед?

  19. KipaTa:

    да не нужно её оптимизировать. php для вычислительных операций — это как-то по-хипстерски. вначале переписать на си, уже потом оптимизировать и профайлить (это если не касаться самого алгоритма, который эм… оригинальный.)

  20. Rerodin:

    Куниформа!

  21. AsaEkb:

    1. Убери собаку из findAngle. Оно генерирует кучу ошибок, что дергает внутренние обработчики, а у некоторых и в лог пишет.
    2. Поиграй к количеством проходов. Не факт, что 2 это оптимально.
    3. Проверь hit rate твоего кэша aka history. Не факт, что он нужен.
    4. Попробуй, если это возможно, перейти к целым числам, заранее посчитав всякие (x-xR)*sin_a.
    5. Сделай нормальные объекты. Не придется извращаться с передачами по ссылке, и код должен стать проще.
    6. Если тебе нужно всего 500 изображений в час, то забей болт на пункты 1-5.

  22. UpaFcuk:

    Спасибо за практичные советы! На днях выложу апдейт. 500 изображений в час будут обрабатываться совместно со вторым скриптом, определяющим, какие документы есть на скане (при многостраничном сканировании) и их точное положение, используя образцы из БД. Он уже готов, работает, использует спектральный анализ, но пока слишком не поворотлив (10 сек.)

  23. UpaFcuk:

    Спектральный анализ — тоже старинный способ.

  24. XbiNo:

    имейдж мэджиком.

  25. UpaFcuk:

    Кстати, вы не знаете, почему в PHP идёт отказ от передачи аргументов по ссылкам? По-моему, это было очень удобно.

  26. AsaEkb:

    Потому что в это почти никогда не нужно, т.к. в php есть zval и массивы и объекты и так передаются по ссылке. http://php.net/manual/en/features.gc.ref… К тому же из-за того же zval есть забавные грабли, типа http://habrahabr.ru/blogs/php/43489/. Зачем убрали указание при вызове — хз. ИМХО стоило его оставить, но сделать обязательным с обоих сторон. Хоть бы читать удобнее было. А то сейчас по вызову вообще не догадаешься, что произойдет.

  27. AsaEkb:

    Хреново сформулировал. Все, а не только массивы и объекты, передается как бы по ссылке, т.е. через zval. Но значение копируется при изменении. Объекты передаются по ссылке всегда.

Добавить комментарий