Я немного поигрался с обработкой изображений и решил почитать о том, как работает цветовое квантование, и после небольшого чтения я нашел алгоритм Modified Median Cut квантования *1002*.
Я читал код реализации C в библиотеке Leptonica и наткнулся на то, что мне показалось немного странным.
Теперь я хочу подчеркнуть, что я далеко не эксперт в этой области, я не математик, поэтому я предсказываю, что все это сводится к тому, что я не понимаю всего этого, а не то, что реализация Алгоритм неверен вообще.
Алгоритм утверждает, что vbox должен быть разбит по самой длинной оси и что он должен быть разбит с использованием следующей логики
Самая большая ось делится путем нахождения ячейки со средним пикселем
(по численности населения), выбрав более длинную сторону и разделив центр
с этой стороны. Мы могли бы просто положить корзину со средним пикселем
в более короткой части, но на ранних стадиях подразделения, это
как правило, кластеры низкой плотности (которые не рассматриваются в
подразделение) в том же Vbox, как часть кластера высокой плотности, что
будет опережать его в среднем цвете Vbox, даже с будущим на основе медианы
подразделения. Используемый здесь алгоритм особенно важен в
ранние подразделения, и 3 полезно для того, чтобы дать видимый, но низкий
Цветовые кластеры населения свои Vbox. Это мало влияет на
подразделение кластеров высокой плотности, которое в конечном итоге будет иметь
примерно равное население в своих ящиках.
Ради аргумента давайте предположим, что у нас есть vbox, который мы находимся в процессе расщепления, и что красная ось является самой большой. В алгоритме Лептоники, в строке 01297, код выглядит следующим образом
- Перебрать все возможные зеленые и синие вариации красного цвета
- Для каждой итерации она добавляет к итоговому количеству пикселей (населению), найденному вдоль красной оси
- Для каждого красного цвета он суммирует совокупность текущего красного и предыдущих, сохраняя, таким образом, накопленное значение для каждого красного
примечание: когда я говорю «красный», я имею в виду каждую точку вдоль оси, которая покрывается итерацией, фактический цвет может быть не красным, а содержать определенное количество красного
Итак, для иллюстрации, предположим, что у нас есть 9 "корзин" вдоль красной оси и что у них есть следующие популяции
4 8 20 16 1 9 12 8 8
После итерации всех красных бинов массив partialsum будет содержать следующий счет для бинов, упомянутых выше
4 12 32 48 49 58 70 78 86
И Итого будет иметь значение 86
Как только это будет сделано, пора выполнить фактическое медианное сечение , а для красной оси это будет выполнено в строке 01346
Перебирает корзины и проверяет накопленную ими сумму. И вот часть, которая выбрасывает меня из описания алгоритма. Он ищет первый контейнер, значение которого больше , чем всего / 2
Не будет total / 2 , что означает, что он ищет корзину, значение которой больше, чем среднее значение, а не медиана ? Медиана для вышеупомянутых бункеров будет 49
Использование 43 или 49 потенциально может оказать огромное влияние на разделение блоков, даже если алгоритм затем перемещается к центру большей стороны где совпавшее значение было ..
Другая вещь, которая меня немного озадачивает, заключается в том, что в документе указано, что корзина со средним значением должна быть расположена, но не упоминается, как поступить, если имеется четное количество корзин. Медиана будет результатом (a + b) / 2 и не гарантируется, что какой-либо из бинов содержит это количество населения. Это то, что заставляет меня думать, что существуют некоторые приближения, которые пренебрежимо малы из-за того, как на самом деле происходит разделение в центре большей стороны выбранного бина.
Извините, если это немного затянулось, но я хотел быть настолько тщательным, насколько мог, потому что это сводило меня с ума уже пару дней;)