Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

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

Секретный алгоритм без запаха

Секрет фокуса — обеспечить неочевидную для других закономерность (в разнице между пахнущими и не пахнущими картами) и увидеть исключения из этой закономерности. Здесь для этого используются простые числа. Вы кладете все карты, соответствующие простым числам, в одну стопку, а остальные — в другую. Пусть в нашем случае туз имеет номер 1, валет — 11, дама — 12, а король — 13. Чтобы отделить простые числа, вы кладете 2, 3, 5, 7, валета и короля в одну стопку, а остальные карты — в другую. Поскольку 1 по определению не относится к простым числам, туз отправляется во вторую стопку. Конечно, запах здесь совершенно ни при чем. Вы учитываете достоинство карт и делите колоду по принципу, известному только вам.

Оставшаяся часть фокуса требует от вас всего лишь уверенности и способности увидеть исключение из простой закономерности — это будет несложное упражнение на сопоставление с образцом. Представьте, что в «пахнущей» стопке находятся карты, соответствующие составным числам. Тогда вам нужно искать карту с простым числом в перетасованной «непахнущей» стопке. Для вас она будет выделяться, как огромная блестящая иголка в стоге сена, в то время как зрители будут видеть просто стог.

Конечно, есть и другие шаблоны, чтобы определить разницу между стопками, — например, класть красные карты в одну, а черные — в другую или фигурные карты в одну, а фоски — в другую, однако это слишком очевидно. Такие шаблоны были бы понятны аудитории, и фокус не получился бы.

Чтобы компьютер видел, важно найти границы

Давайте теперь перейдем к более сложному явлению — возможности компьютера увидеть мир. Для этого мало подсоединить к нему камеру. Компьютер должен уметь определять, что присутствует на картинке, — находить шаблоны и понимать, каким предметам они соответствуют, то есть знать, чтó он видит. Только в этом случае мы и правда сможем утверждать, что он «видит».

Наш мозг постоянно находит шаблоны в изображениях и сопоставляет их с образцами. Свет, поступающий в глаз, преобразуется в сетчатке, которая находится в задней части глазного яблока, в сигналы, идущие в мозг. Эта информация обрабатывается с целью нахождения интересных шаблонов, форм и в конечном итоге предметов. Мы продолжаем узнавать новое о зрении человека, но возможность снабдить компьютер или робота способностью видеть — важная и трудная техническая задача. Она подразумевает разработку алгоритмов, которые обучат компьютеры замечать образцы в увиденном. Одна из фундаментальных способностей человеческого мозга, позволяющая распознавать предметы, — умение находить их границы. Мозг видит линии. Как стало понятно в случае с векторными изображениями, линии — это первый шаг к формам, а затем — к предметам. Так как же «увидеть» линии?

Во-первых, давайте рассмотрим очень-очень скучную картинку (рис. 64a). Как и все компьютерные изображения, она представлена в цифровом виде и состоит из пикселов. Обычно изображение состоит из многих тысяч пикселов. Конечно же, реальный мир из них не состоит! Это просто представление изображения. У каждого пиксела есть присвоенные ему место, особый цвет и яркость. В нашей скучной картинке всего 32 пиксела и два оттенка серого — посветлее и потемнее. Но при взгляде на нее становится ясно, что здесь есть кое-что интересное — вертикальная граница там, где светло-серый с одной стороны сменяется темно-серым с другой. Сама по себе эта граница не является линией пикселов, это всего лишь разница между ними. Мы видим ее только потому, что наш мозг совершает много операций по обработке изображения.

Чтобы написать алгоритм, который позволит компьютеру определить края, необходимо хорошее представление. Изображение легко представить в виде набора чисел, используя разные значения для светло-серого и темно-серого. Благодаря этому мы используем математику в алгоритмах обработки. Условимся, что светло-серый — это число 3, а темно-серый — 4. Например, эти числа могли бы показывать количество чернил, необходимое для печати пиксела. Изображение только из чисел показано на рис. 64b.

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

Теперь давайте посмотрим на еще более мелкий и скучный образец, представленный на рис. 65. Он состоит всего лишь из трех пикселов, однако, надо признать, в нем есть отрицательное число, что делает его немного более интересным. Но как это поможет компьютеру видеть нечто простое? В информатике такой шаблон называется цифровым фильтром. Как и любой фильтр, например в кофеварке, он пропускает лишь нечто определенное. В данном случае — определенные наборы чисел вместо кофе.

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

Рассмотрим пример. Допустим, входной набор чисел, представляющий изображение, — 3, 3, 3, 4, 4, 4. Мы применяем к нему фильтр. Как это будет выглядеть для первых трех чисел, показано на рис. 66а. Мы умножаем фильтр на соответствующие числа, получаем −3, 0 и 3, потом складываем их и получаем 0. Это новое значение на выходе фильтра. Теперь фильтр перемещается, словно на конвейере, на один элемент. Он накладывается на новые входные цифры и дает следующий результат на выходе, как показано на рис. 66b. Пожалуйста, двигайтесь дальше! Фильтр сдвигается еще на один шаг, нависает над новыми числами и дает следующий результат. Получается как на рис. 67a. Наконец, передвинувшись еще на один шаг вправо, наш трудолюбивый фильтр доходит до конца, и на выходе появляется последний результат, как на рис. 67b.

Что вообще такое структура изображения?