Подсчет объектов на картинке на C

> сколько пикселей попало в круг с определённым радиусом, увеличить радиус и снова посчитать число пикселей.

С кругами к сканированию массива ещё считать придётся, плюс непонятки на пограничных пикселах.. Квадраты лучше.

> Квадраты лучше.

круг инвариантен к вращению, а квадрат не особо

почему-же? например капчу на лоре разгадывать, лол

>С кругами к сканированию массива ещё считать придётся, плюс непонятки на пограничных пикселах. Квадраты лучше.

После прочтения: М.Ласло Вычислительная геометрия и компьютерная графика на с++ (18574.62Kb djvu) http://www.studfiles.ru/component/option,com_mtree/task,viewlink/link_id,1643...

спорить будет не о чем.

P.S. "Всё уже украдено до нас..." (с) "Операция Ы" :)

> Уточни, GNU General ли Public License, а то непонятно.

мне пофиг кто его и где будет использовать и как. Такое уточнение сойдет?

>умеет ли матлаб брать видеокартинку с устройства видеозахвата? умеет

Вообще новость - полный велосипедобаян. Автор молодец, что развивается и учится, а вот модеры на ЛОРе как всегда во всей красе. Как это вообще новостью назвать то можно?! Есть просто море библиотек, позволяющих реализовывть подобное в 3х строках кода: OpenCV, ITK, VIPS... их просто не счесть в данный момент.

Нормально все! Чем больше велосипедов, тем лучше экология. Метан - наше новое топливо!

просто дай код и инструкции. хочу. правда уже хуже, чем раньше. да ЛОР для меня не школа. но дай. просто дай код и инструкции. вот.

try OpenCV

> Так одним пьяным русским был заложен базис программы "Скайнет" и планета Земля неотвратимо почесала к собственному капцу.

не могу тебе не ответить цитатой, уж очень больно она мне понравилась(относительно начала футбола Испания-Россия):

через 10 сек поиска по сайту понял, что похоже топик стерли. но я его сохранил:

==================================

ОЛЕ-ОЛЕ-ОЛЕ!!!!

Пьяная толпа радостно скандировала про футбол пад окнами. Запустил с балкона в них петардой, попал одному прямо в тыкву, и она одновременно с этим и взорвалась! Сейчас этого придурка увозят с окрававленной башкой на скорой (но ходить он сам может)! ОЛЕ-ОЛЕ-ОЛЕ!!!!

==================================

вот тебе скайнет.

> Респект, применить пока не где но почитать исходники стоит

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

> кстати, откуда такая интересная запись Бернстейновского алгоритма?

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

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

> Этот алгоритм выделяет четырхсвязные границы. Чтобы выделять 8-мисвязные границы нужно в цикл добавить еще пару условий.

Что такое n-связные границы?

> OpenCV, ITK, VIPS.

действительно - "детский сад". In medical image processing
(есть даже целый раздел), астрофизике, видео контроле, все испахано
в доль и поперек. Извини, vilfred, с некотрых пор занимаюсь этим
профессионально.

многоугольники. gb2school

ну так и докажи это при помощи новости на ЛОР, что c помощью OpenCV (с приведением исходного кода, пошаговой инструкцией, как собирать/как компилировать и т.п. и т.д.) возможно сделать то-же самое... можно быть немного менее голосоловным, скажем так?

>while (*key) { >hash = (hash * 33) ^ *key++; >}

И у Кнута отлично описано, почему это плохой хэш. Use jenkins hash: http://burtleburtle.net/bob/hash/index.html

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

Ну существует платформы, где умножение быстрее смещения.

>c помощью OpenCV
не обязательно OpenCV ...
Мое утверждение, что в области, где работаю (связанная с медициной),
есть целый под-раздел, под названием Image Segmentation,
где одних только edge detection algorithms - 10ки
(btw, алгоритм, который используется в коде имеет имя собстевенное,
избрел его наш русский товаришч)
и существует 10ки open source tookits/libs, 10ки публикаций,
которые эту/подобную задачку давно решили.
т.е. новость тянет только на "домашнее задание" для студента
"факультета информационных технолгий".

Если бы был приведен код, который по инфракрасному
излучению кровеносных сосудов расположенных на
голове, (рисунок уникален для каждого
человека, aka "печать зверя"), позволяющий
идентифицировать (по потоку снимаемому с инфракрасной
веб-камеры) какого-то конкретного человека -
я бы сказал "Молодца!" :)

> Ну существует платформы, где умножение быстрее смещения.

вот только ненадо категоричных выкриков.
я не помню на вскидку где это есть, но то что есть это 100%.
и логика "алгоритм проще поэтому быстрее" тут не работает.

> многоугольники. gb2school

Что многоугольники, где ты там увидел связность? Еще раз повторяю вопрос, что в данном случае называется 2-х, 4-х и n-связными областями?

> И у Кнута отлично описано, почему это плохой хэш. Use jenkins hash

кнут может писать все что угодно, но без тестов это лишь вода.
в составе "OSSP act" есть файлик (act_hash_fct.c), содержащий тесты/результаты разных алгоритмов и описание их плюсов и минусов.
алгоритм дженкинса в 2 раза медленее, а распределение почти 1:1.

>вот только ненадо категоричных выкриков. я не помню на вскидку где это есть, но то что есть это 100%.

Нет. Смещение выполняется за один такт (пол такта если АЛУ работает по уровню), умножение будет четверть такта? :)

>и логика "алгоритм проще поэтому быстрее" тут не работает.

Дело не в логике алгоритма, а в физическом АЛУ, которое выполняет смещение за один такт. Максимум умножение будет с такой же скоростью - в современных процессорах (ppro+) умножение в два раза медленнее.

>кнут может писать все что угодно, но без тестов это лишь вода.

Вы наверное не знаете, кто такой Кнут.

>в составе "OSSP act" есть файлик (act_hash_fct.c), содержащий тесты/результаты разных алгоритмов и описание их плюсов и минусов. алгоритм дженкинса в 2 раза медленее, а распределение почти 1:1.

Это вы на картинке увидели, что оно почти 1:1? В общем случае это называется FNV хэш, с "неудобным" размером хэшируемых данных у него проблемы.

где ты там увидел "области"?

Что изменить в проге твоей надо чтобы объектов количество только выводило?

все, не перле модуль нашел я. разобрался уже. давай, ещо пиши.

> В общем случае это называется FNV хэш, ...

Как это? Это совершенно не FNV хэш, в FNV умножается на FNV primes, который никак не 33...

> И у Кнута отлично описано, почему это плохой хэш.

Можно ссылку? Я пролистал главу 6.4 -- не нашел...

В любом случае, на практике это нынче самый распространенный кэш.

> Нет. Смещение выполняется за один такт (пол такта если АЛУ работает
> по уровню), умножение будет четверть такта? :)

Гы гы :) А вполне может быть. Почему ты такую возможность сразу исключаешь?

Сравнение хешей, смотреть тут: http://smallcode.weblogs.us/2008/06/17/murmur-hash/

А есть ли практическая реализация для этой библиотеки? К примеру, она могла бы стать основой системы сортировки больших коллекций фотографий. Интерес совершенно не праздный, так как поиск изображений в такой коллекции и ее упорядочивание -- одно из самых нудных занятий в течении моего рабочего дня :)

>Как это? Это совершенно не FNV хэш, в FNV умножается на FNV primes, который никак не 33...

FNV это просто умножение на простые множители, Fowler, Noll и Vo выбрали одни числа, Бернштейн - другие, кто-то третьи.

Тип смешивания бит от этого не меняется.

>Гы гы :) А вполне может быть. Почему ты такую возможность сразу исключаешь?

Дело в том, что процессор (АЛУ или любой другой) - это дискретное устройство, поэтому оно может обрабатывать данные (читать, писать и т.п.) только на отсчетах собственного генератора. Никак иначе дискретное устройство работать не может. Поэтому процессор не может считывать значение из регистра раньше такта (или спада/подъема уровня, но это и есть тот самый такт).

Странно, что вы это не понимаете.

>Можно ссылку? Я пролистал главу 6.4 -- не нашел...

Ошибся, Jenkins hash article. See below.

>В любом случае, на практике это нынче самый распространенный кэш.

Не может быть, это очень печально...

If your keys are lowercase English words, this will fit 6 characters into a 32-bit hash with no collisions (you'd have to compare all 32 bits). If your keys are mixed case English words, 65*hash+key[i] fits 5 characters into a 32-bit hash with no collisions. That means this type of hash can produce (for the right type of keys) fewer collisions than a hash that gives a more truly random distribution. If your platform doesn't have fast multiplies, no sweat, 33*hash = hash+(hash<<5) and most compilers will figure that out for you.

On the down side, if you don't have short text keys, this hash has a easily detectable flaws. For example, there's a 3-into-2 funnel that 0x0021 and 0x0100 both have the same hash (hex 0x21, decimal 33) (you saw that one coming, yes?).

А я написал хелловорлд.

> Поэтому процессор не может считывать значение из регистра раньше
> такта (или спада/подъема уровня, но это и есть тот самый такт).

А если на ядре выполняется две инструкции за один такт - это как? А четыре? А в контексте топика это очень даже возможно. Странно что вы это не понимаете.

>А если на ядре выполняется две инструкции за один такт - это как? А четыре? А в контексте топика это очень даже возможно. Странно что вы это не понимаете.

Умножение-то так не параллелится.

Одна операция не может быть быстрее одного такта (не считая случая, когда такт считается по уровню), согласны хоть с этим? :)

>>Можно ссылку? Я пролистал главу 6.4 -- не нашел...

> Ошибся, Jenkins hash article. See below.

В смысле, ты ошибся, сославшиcь на Кнута вместо Дженкинса?

> ...if you don't have short text keys,...

А этот хэш и применяется (широко) для текстовых ключей.

> For example, there's a 3-into-2 funnel that 0x0021 and 0x0100 both have the same hash

Гы!

Вот про это Грэйс писАл, что всякий раз думать надо... Мне это напоминает боттлнек у квиксорта с медианным опорным элементом (можно заработать, если _очень_ постараться)...

:-)

> FNV это просто умножение на простые множители, Fowler, Noll и Vo выбрали одни числа, Бернштейн - другие, кто-то третьи.

33 -- отнюдь не простое число. И FNV простые числа не с потолка брали.

> Тип смешивания бит от этого не меняется.

Меняется! У FNV их primes подобраны по некоему хитрому закону (который и призван обеспечить надлежащее смешивание), а 33 -- это просто сдвигаем влево на 5, а на освободившееся место воспроизводим младшие 5 бит как есть.

> Умножение-то так не параллелится.

Умножение чего? Элементов матрицы?

> Одна операция не может быть быстрее одного такта (не считая случая, когда такт
> считается по уровню), согласны хоть с этим? :)

В рамках того что я знаю - согласен :).

Вдогонку:

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

>где одних только edge detection algorithms - 10ки а какова их вычислительная сложность? а видел и такие, что одну картинку могут несколько минут обсчитывать, хоть и с хорошим результатом к сожалению, в около-real-time задачах такое непримелемо

>Дженкинсовский хэш близок к идеалу в смысле распределения, но шибко тормозит, раза в 2 по сравнению с Бернстейновским. Но даже в хужшем возможном на практике случае, разница в кол-ве коллизий (с точки зрения перформанса) пренебрежима. Чего не скажешь о времени вычисления хэша для длинных строковых ключей.

Есть такое дело... 9 операций на 4 байта IIRC, но для хэширования 2 и 3 32битных слов дженкинс был очень оптимизирован, так что может быть использован при хэшировании IP адресов.

>В смысле, ты ошибся, сославшиcь на Кнута вместо Дженкинса?

Yep.

>Вот про это Грэйс писАл, что всякий раз думать надо... Мне это напоминает боттлнек у квиксорта с медианным опорным элементом (можно заработать, если _очень_ постараться)...

Всегда есть люди, которые постараются это сделать, если доберутся :)

>> Умножение-то так не параллелится.

>Умножение чего? Элементов матрицы?

Прочтите еще раз, о чем речь: об умножении числа на число и сдвиг числа на несколько бит.

>Меняется! У FNV их primes подобраны по некоему хитрому закону (который и призван обеспечить надлежащее смешивание), а 33 -- это просто сдвигаем влево на 5, а на освободившееся место воспроизводим младшие 5 бит как есть.

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

При этом и FNV и Бернштейн сделали один и тот же хэш: пермутация бит с 1 при умножении и освобождение их места для следующего элемента, при этом биты выбраны так, чтобы при каждом умножении были переполнения разрядов, и освобождались младшие биты. У Бернштейна попроще, но идея та же.

Например дженкинс в этом плане совсем другой - там хочешь-на хочешь, но все биты перемешиваются с входным словом, т.е. нет такого слова, которое приводит к нарушению логики хэша (как в случае с fnv и Бернштейном).

Хотя с другой стороны, первая версия дженкинса, используемая в ядре Linux для хэширования IP адресов и портов, состоит из 9 раундов, облегченный до 2 раундов дженкинс был взломан: для заданного хэша можно сгенерировать такие входные данные, что хэш совпадет.

> Прочтите еще раз, о чем речь: об умножении числа на число и сдвиг
> числа на несколько бит.

Это вы так неверно ставите задачу. Задача была распознать множество клякс на картинке.

>Это вы так неверно ставите задачу. Задача была распознать множество клякс на картинке.

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