Так я ж вас и спрашиваю, может ли ваш алгоритм работать в атономном режиме? Вы же сразу начали про «закапывание идей» :)
>Но если я моделирую перемещение фокуса внимания вдоль забора, то достаточно точно позиционируюсь.
Дык для того что бы программа сама моделировала движение вдоль забора, она должна «понимать» где этот забор. А этого ж как раз и нет.
>Что касается ручного режима, то тривиально делается автоматическое перемещение фокуса внимания на случайный вектор или даже лучше с учетом градиента в предыдущей локальной области
Если вы будете перемещать «фокус внимания» случайным образом, ваш алгоритм работать не будет, ибо он основан на том, что вы перемещаетесь вдоль какого-либо объекта, а не произвольно.
Поправте меня, если я не прав.
Ну так ничего интересного из теории не появляется, потому и писать не о чем…
Что касается построения карт глубин, то самые лучшие результаты дают вроде бы алгоритмы на марковских цепях, но что-то они настолько сложные что я так и не смог их толком понять :)
>Ваш вопрос показывает как свободную мысль загоняют в рамки шаблонных решений
Боже упаси :) Я просто позиционирую данный алгоритм. Это не есть алгоритм сопоставления областей изображения. Области вы сопоставляете простым сравнением локальной области.
>Я предлагаю способ как сопоставлять две области на изображениях.
Правильно это фраза должна звучать «Я предлагаю способ как вручную сопоставлять две области на изображениях», потому что алгоритм без вас этого сделать не может.
>Хотите построить карту глубины — походите подольше по всему кадру.
Это не алгоритм…
Правильно я понимаю, что построить карту глубины в автоматическом режиме этим методом нельзя? А какова тогда его практическая ценность?
Particle Filter это конечно здорово, но задачу «сопоставления «одной и той же точки» на двух изображениях» он не решает в общем случае.
>На счет бесконечных чисел вообще не понял. Вы про числа с плавающей запятой? Ну так то отдельная история.
Для представления произвольного числа в СОК требуется набор простых чисел. Но этот набор в общем случае неизвестен, поскольку неизвестны все простые числа и нет формулы для их вычисления. Поэтому нельзя говорить, что в СОК представимы все числа.
Ну это я немного занудствую конечно, потому что на практике известно достаточно большое количество простых чисел, тем не менее… :)
>Для совместимости устройств есть достаточно быстрое прямое и обратное преобразование в двоичные числа.
Оно то да, только это не удобно. Кроме того теряется такое преимущество как помехоустойчивость.
Смущает то, что хранение числа в остатках занимает больше памяти, чем хранение в двоичном виде. Да еще и для хранения каждого остатка требуется различное число бит.
Другой недостаток — позиционная система может представлять бесконечно большие числа. А система с остатками — нет. Да к тому же и сами основания можно выбирать произвольно, а это значит что может быть несовместимость с другими девайсами.
В общем, для сугубо специализированных устройств может эта система и имеет преимущества, но для универсальных устройств — наврядли подходит.
>Программа перебирают случайным образом несколько миллионов игр, которые могут быть сыграны из текущего положения. Причём каждая игру проигрывается до конца,
Что-то вот здесь не очень ясно. Как можно просчитать партию до конца? Допустим на каждом ходу есть 30 вариантов хода. Допустим, партия длится 40 ходов. Общее числ вариантов — 30^40. Это понятно. Теперь, допустим что первый ход мы делаем не любой, а лишь из случайно отобранных 5 ходов. Значит число вариантов уже не 30^40 а 5*30^39 то есть примерно 30^39. Но это число не намного лучше исходного. Фактически случайный выбор первого хода ничего не дает. Полный перебор пяти партий по 30^39 вариантов в каждой по прежнему невозможен.
Значит имеется ввиду, что случано будут отбираться ходы не только на первом ходу, но и на всех ходах. Тогда мы получим значительное сокращение числа варинатов: 5^40. Это конечно тоже дофига, но все таки получше. Но тут возникает проблема. При таком подходе точность очень сильно зависит от выбора этих самых 5 ходов. Если их выбирать случайным образом то исходы будут совершенно отфонарные. Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Преобразования Хафа не пробовали? В принципе я не особый сторонник Хафа, но в данном случае они наверно могут дать не самый плохой вариант. Поскольку вы ищите только линии, причем под определнном углом, то Хаф напрашивается сам собой. При этом, Хаф сможет найти эти линии, даже если они пунктиром.
Спасибо за полезную информацию.
Один вопрос — я так понимаю, этот метод годится только для неподвижной камеры? А если изображение дрожит? И фон имеет небольшие постоянные сдвиги? Тогда градиентный метод наверно работать не будет?
Во-первых. Методы на основе хааровских фильтров предназначены для полутонового изображения. Их применение к смешанным полутоново-контурным изображениям — не оправдано. Почему? Потому что они на самом деле более чувствительны, чем детектор Канни. Например — плавный градиент хорошо детектируется Хааром, но совсем не детектируется Канни. Значит, обнаружение плавных переходов будет только ухудшаться в вашем методе.
Далее. Что именно вы пытаетесь улучшить, введя границы в полутоновое изображение? Допустим, в некторой области изображения проходит граница. Детектор хаара ее обнаружит (допустим, даст отклик d=10). Обрабатывая изображение с вычтенным контуром, детектор ее тоже обнаружит (допустим будет d=20). Да, абсолютное значение детектора будет выше, но что это дает? Вы с успехом можете умножать d на два и результат будет точно такой как с полутоново-конутрным изображением. Я что пытаюсь сказать — если граница есть, хаар ее обнаружит в любом случае. То, что вы делаете просто увеличивает дисперсию отклика детектора. Но эту дисперсию можно увеличить просто увеличив контрастность изображения, к примеру. Результат будет тот же (только без артефактов, как в вашем методе, см ниже).
И еще, ваши манипуляции могут ухудшить работу фильтров:
Второе. Смешивание полутонового и наращенного контурного изображений порождает артефакты. Пример:
Да и еще, почему вы именно вычитаете Канни из полутоновго, а не прибавляете, к примеру? Получается эти контуры не будут видны на темном изображении. Из черного вы будете вычитать белое, и что? Получится все равно черное. А как же быть с неграми?
В-третьих — введение новых примитивов в метод Виолы-Джонса — не окажет особого влияния на его эффективность. Почему? Потому что фильтры Хаара берутся не с потолка. Фильтры Хаара образуют полный ортогональный базис (вейвлетный базис). Это значит что любые другие примитивы могут быть расписаны через базовые. А значит введение новых примитивов — ну может немного увеличит быстродействие, но на качество распознавания особого влияния не окажет.
Да и вообще, применение Хаара для распознавния микроэмоций — слишком грубый метод, как на мой взгляд. Вы же сами писали статью про рынок программ распознавания эмоций. Разве там применяется Виола-Джонс? Этот метод хорош только для поиска самого лица. Для микроэмоций — нет.
Ну и в-четвертых, статья лишком сумбурно написана. Я до сих пор не могу толком понять о чем она. То ли вы описываете как работает детектор Канни, то ли пытаетесь усовершенствовать Виолу-Джонса. Цели ваших действий нечетко описаны. В выводах вы пишете «С помощью таких апгрейдов возможно теоретическое улучшение метода.» Так где эта теория, подтверждающая, что ваш метод действительно лучше классического Виолы-Джонса? Теория как раз говорит об обратном. Если вы на практике докажете что этот метод лучше — ура, мы порадуемся вместе, если нет — ну отрицательный результат тоже результат :)
Не принимайте близко к сердцу, вы молодец что работаете в этом направлении, успехов :)
А, я наконец-то понял. Вы реализуете Канни вручную, а внутри него применяется оператор Собела.
Просто в графичсеких библиотеках Канни обычно уже реализован, и применять Собела для него не нужно.
Какова роль оператора Собеля? Для чего он здесь? На бинаризацию он не влияет, для Канни он тем более не нужен.
И еще, почему бы не использовать адаптивную бинаризацию вместо древнего Оцу? Результат обычно намного лучше.
>Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.
Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
>не очень известного, но крайне интересного иерархического метода
Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
1) «Границы: Поэтому этот класс признаков может служить только глубоко вспомогательным.» Ну я бы не стал гвоорить о «глубоко вспомогательности». Во первых, есть конутрный анализ, который справляется с некторыми задачами очень хорошо. Во-вторых есть ряд методов, основанных на диаграмме градиентов, которые тоже используются неплохо. А некоторые системы (например распознавание человека) работают только на анализе гистограммы градиентов.
2) «Текстуры: Соответственно эти признаки тоже могут быть только вторичными, хотя их значение несколько больше.» Угу, «несколько больше». Посмотрите, например метод «Integrated Region Matching». Там очень хорошие результаты, основанные в основном на анализе текстур. Кроме того, текстурный метод использует большинство систем поиска изображений по контенту.
3) «SIFT не найдет котенка». Да, котенка не найдет, а вот здание, например, найдет с разных ракурсов.
4) «Цвет является, пожалуй, наиболее значимой для анализа характеристикой». Ну это вы завернули :) В ч/б изображении содержится 90% информации об изображении. Вы без труда узнаете человека на ч/б фотографии. А попробуйте его узнать по спектрограмме ;) Да гугл, может и ищет по цвету, но только после того как не смог найти по другим признакам. Так что на «самую значимую» характеристику цвет не катит. Я понимаю, тех, кто только начинает разработку подобных систем, привлекает спектрограмма своей простотой. Но в дальнейшеам оказывается, что это тупиковый путь.
n) Некторые методы вообще не рассмотрены. Например, вейвлетные (фильтры Хаара и т.п.). А ведь для распознавания лиц, от того же гугла, работает только с помощью этих методов.
В принципе вы молодец, что поднимаете эту тему, но нужно быть более аккуратными с выводами. Иначе у читающих могут возникнуть неправильные представления о теме.
На самом деле, о вопросе размещения значимых и референс типов действительно нужно останавливаться более подробно. Я часто провожу собеседования, и всегда задаю вопрос о различии структур и классов. Так вот, все как один отвечают что «структуры хранятся в стеке, а классы — в куче». Когда им приводишь такой пример class A
{
int i;
} и спрашиваешь, где находится i — большинство кандидатов впадают в ступор.
Эээ… а что именно тянет-то?
Разве автор предложил что-то новое?
Распознавание символов — нейронной сетью. Сегментация — по ретроспективе росчерков, а значит не годится для распознавания изображений (что, кстати, кардинально отличет даный проект от ТБВ). То, что индекс стоит выше символа — как бы и так понятно. А больше ничего и нет…
Спасибо за статью. По моему, в OpenCV применяется похожий алгоритм.
>Сложность такого алгоритма пропорциональна количеству точек внешних контуров для объектов изображения.
По факту, это означает сложность O(n^2). Такая сложность практически у всех алгоритмов (в т.ч. и у простейших рекурсивных). Я конечно понимаю, что ваш алгоритм быстрее, но это достигается уменьшением константы вычислений, а не снижением сложности алгоритма.
Странно, что в статье ни слова про главную проблему такого подхода — отвод тепла.
Мне всегда казалось, что микросхемы делают плоскими, а не «кубиком» именно потому, что так легче отвести тепло. Ведь теплоемкость обратно пропорциональна площади поверхности и прямо пропорциональна объему. Здесь же площадь поверхности — практически та же, зато объем «подрос». А значит транзистор будет больше нагреваться (даже несмотря на снижение энергопотребления). А тепло — враг электроники, оно сначала снижает электрические характеристики, а затем разрушает микросхему.
>Но если я моделирую перемещение фокуса внимания вдоль забора, то достаточно точно позиционируюсь.
Дык для того что бы программа сама моделировала движение вдоль забора, она должна «понимать» где этот забор. А этого ж как раз и нет.
>Что касается ручного режима, то тривиально делается автоматическое перемещение фокуса внимания на случайный вектор или даже лучше с учетом градиента в предыдущей локальной области
Если вы будете перемещать «фокус внимания» случайным образом, ваш алгоритм работать не будет, ибо он основан на том, что вы перемещаетесь вдоль какого-либо объекта, а не произвольно.
Поправте меня, если я не прав.
Что касается построения карт глубин, то самые лучшие результаты дают вроде бы алгоритмы на марковских цепях, но что-то они настолько сложные что я так и не смог их толком понять :)
Боже упаси :) Я просто позиционирую данный алгоритм. Это не есть алгоритм сопоставления областей изображения. Области вы сопоставляете простым сравнением локальной области.
>Я предлагаю способ как сопоставлять две области на изображениях.
Правильно это фраза должна звучать «Я предлагаю способ как вручную сопоставлять две области на изображениях», потому что алгоритм без вас этого сделать не может.
>Хотите построить карту глубины — походите подольше по всему кадру.
Это не алгоритм…
Particle Filter это конечно здорово, но задачу «сопоставления «одной и той же точки» на двух изображениях» он не решает в общем случае.
Для представления произвольного числа в СОК требуется набор простых чисел. Но этот набор в общем случае неизвестен, поскольку неизвестны все простые числа и нет формулы для их вычисления. Поэтому нельзя говорить, что в СОК представимы все числа.
Ну это я немного занудствую конечно, потому что на практике известно достаточно большое количество простых чисел, тем не менее… :)
>Для совместимости устройств есть достаточно быстрое прямое и обратное преобразование в двоичные числа.
Оно то да, только это не удобно. Кроме того теряется такое преимущество как помехоустойчивость.
Другой недостаток — позиционная система может представлять бесконечно большие числа. А система с остатками — нет. Да к тому же и сами основания можно выбирать произвольно, а это значит что может быть несовместимость с другими девайсами.
В общем, для сугубо специализированных устройств может эта система и имеет преимущества, но для универсальных устройств — наврядли подходит.
Что-то вот здесь не очень ясно. Как можно просчитать партию до конца? Допустим на каждом ходу есть 30 вариантов хода. Допустим, партия длится 40 ходов. Общее числ вариантов — 30^40. Это понятно. Теперь, допустим что первый ход мы делаем не любой, а лишь из случайно отобранных 5 ходов. Значит число вариантов уже не 30^40 а 5*30^39 то есть примерно 30^39. Но это число не намного лучше исходного. Фактически случайный выбор первого хода ничего не дает. Полный перебор пяти партий по 30^39 вариантов в каждой по прежнему невозможен.
Значит имеется ввиду, что случано будут отбираться ходы не только на первом ходу, но и на всех ходах. Тогда мы получим значительное сокращение числа варинатов: 5^40. Это конечно тоже дофига, но все таки получше. Но тут возникает проблема. При таком подходе точность очень сильно зависит от выбора этих самых 5 ходов. Если их выбирать случайным образом то исходы будут совершенно отфонарные. Вероятность попасть в «правильные» партии — это примерно как попасть из ружья в утку с закрытыми глазами, причем 40 раз подряд!
Автор, можете прояснить этот момент?
Один вопрос — я так понимаю, этот метод годится только для неподвижной камеры? А если изображение дрожит? И фон имеет небольшие постоянные сдвиги? Тогда градиентный метод наверно работать не будет?
Во-первых. Методы на основе хааровских фильтров предназначены для полутонового изображения. Их применение к смешанным полутоново-контурным изображениям — не оправдано. Почему? Потому что они на самом деле более чувствительны, чем детектор Канни. Например — плавный градиент хорошо детектируется Хааром, но совсем не детектируется Канни. Значит, обнаружение плавных переходов будет только ухудшаться в вашем методе.
Далее. Что именно вы пытаетесь улучшить, введя границы в полутоновое изображение? Допустим, в некторой области изображения проходит граница. Детектор хаара ее обнаружит (допустим, даст отклик d=10). Обрабатывая изображение с вычтенным контуром, детектор ее тоже обнаружит (допустим будет d=20). Да, абсолютное значение детектора будет выше, но что это дает? Вы с успехом можете умножать d на два и результат будет точно такой как с полутоново-конутрным изображением. Я что пытаюсь сказать — если граница есть, хаар ее обнаружит в любом случае. То, что вы делаете просто увеличивает дисперсию отклика детектора. Но эту дисперсию можно увеличить просто увеличив контрастность изображения, к примеру. Результат будет тот же (только без артефактов, как в вашем методе, см ниже).
И еще, ваши манипуляции могут ухудшить работу фильтров:
Второе. Смешивание полутонового и наращенного контурного изображений порождает артефакты. Пример:
Да и еще, почему вы именно вычитаете Канни из полутоновго, а не прибавляете, к примеру? Получается эти контуры не будут видны на темном изображении. Из черного вы будете вычитать белое, и что? Получится все равно черное. А как же быть с неграми?
В-третьих — введение новых примитивов в метод Виолы-Джонса — не окажет особого влияния на его эффективность. Почему? Потому что фильтры Хаара берутся не с потолка. Фильтры Хаара образуют полный ортогональный базис (вейвлетный базис). Это значит что любые другие примитивы могут быть расписаны через базовые. А значит введение новых примитивов — ну может немного увеличит быстродействие, но на качество распознавания особого влияния не окажет.
Да и вообще, применение Хаара для распознавния микроэмоций — слишком грубый метод, как на мой взгляд. Вы же сами писали статью про рынок программ распознавания эмоций. Разве там применяется Виола-Джонс? Этот метод хорош только для поиска самого лица. Для микроэмоций — нет.
Ну и в-четвертых, статья лишком сумбурно написана. Я до сих пор не могу толком понять о чем она. То ли вы описываете как работает детектор Канни, то ли пытаетесь усовершенствовать Виолу-Джонса. Цели ваших действий нечетко описаны. В выводах вы пишете «С помощью таких апгрейдов возможно теоретическое улучшение метода.» Так где эта теория, подтверждающая, что ваш метод действительно лучше классического Виолы-Джонса? Теория как раз говорит об обратном. Если вы на практике докажете что этот метод лучше — ура, мы порадуемся вместе, если нет — ну отрицательный результат тоже результат :)
Не принимайте близко к сердцу, вы молодец что работаете в этом направлении, успехов :)
Просто в графичсеких библиотеках Канни обычно уже реализован, и применять Собела для него не нужно.
И еще, почему бы не использовать адаптивную бинаризацию вместо древнего Оцу? Результат обычно намного лучше.
Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
1) «Границы: Поэтому этот класс признаков может служить только глубоко вспомогательным.» Ну я бы не стал гвоорить о «глубоко вспомогательности». Во первых, есть конутрный анализ, который справляется с некторыми задачами очень хорошо. Во-вторых есть ряд методов, основанных на диаграмме градиентов, которые тоже используются неплохо. А некоторые системы (например распознавание человека) работают только на анализе гистограммы градиентов.
2) «Текстуры: Соответственно эти признаки тоже могут быть только вторичными, хотя их значение несколько больше.» Угу, «несколько больше». Посмотрите, например метод «Integrated Region Matching». Там очень хорошие результаты, основанные в основном на анализе текстур. Кроме того, текстурный метод использует большинство систем поиска изображений по контенту.
3) «SIFT не найдет котенка». Да, котенка не найдет, а вот здание, например, найдет с разных ракурсов.
4) «Цвет является, пожалуй, наиболее значимой для анализа характеристикой». Ну это вы завернули :) В ч/б изображении содержится 90% информации об изображении. Вы без труда узнаете человека на ч/б фотографии. А попробуйте его узнать по спектрограмме ;) Да гугл, может и ищет по цвету, но только после того как не смог найти по другим признакам. Так что на «самую значимую» характеристику цвет не катит. Я понимаю, тех, кто только начинает разработку подобных систем, привлекает спектрограмма своей простотой. Но в дальнейшеам оказывается, что это тупиковый путь.
n) Некторые методы вообще не рассмотрены. Например, вейвлетные (фильтры Хаара и т.п.). А ведь для распознавания лиц, от того же гугла, работает только с помощью этих методов.
В принципе вы молодец, что поднимаете эту тему, но нужно быть более аккуратными с выводами. Иначе у читающих могут возникнуть неправильные представления о теме.
class A
и спрашиваешь, где находится i — большинство кандидатов впадают в ступор.{
int i;
}
Разве автор предложил что-то новое?
Распознавание символов — нейронной сетью. Сегментация — по ретроспективе росчерков, а значит не годится для распознавания изображений (что, кстати, кардинально отличет даный проект от ТБВ). То, что индекс стоит выше символа — как бы и так понятно. А больше ничего и нет…
>Сложность такого алгоритма пропорциональна количеству точек внешних контуров для объектов изображения.
По факту, это означает сложность O(n^2). Такая сложность практически у всех алгоритмов (в т.ч. и у простейших рекурсивных). Я конечно понимаю, что ваш алгоритм быстрее, но это достигается уменьшением константы вычислений, а не снижением сложности алгоритма.
Мне всегда казалось, что микросхемы делают плоскими, а не «кубиком» именно потому, что так легче отвести тепло. Ведь теплоемкость обратно пропорциональна площади поверхности и прямо пропорциональна объему. Здесь же площадь поверхности — практически та же, зато объем «подрос». А значит транзистор будет больше нагреваться (даже несмотря на снижение энергопотребления). А тепло — враг электроники, оно сначала снижает электрические характеристики, а затем разрушает микросхему.