Патент ссср 427351

 

Союз Советских

Социалистимеских

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (11) 427351 (61) Зависимое от авт. свид-ва(22) Заявлено 14 12.71 (21) 172502 3/18-24 (51) М. Кл. G 06 Ic 11/00

-Q 06 К 7/14 с присоединением заявки №

Гасударственный комитет

Совета теиннстрое СССР ао делам изобретений н открытий

4 (3 2) Приоритет (43) Опубликовано 05.05 74 Бюллетень № 17 (53) УДК 621,391.19 (088.8) (45) Дата опубликования описания 05.06.75

1"

t

1 (72) Авторы изобретения

В. А„ Леонтьев (71) Заявитель Ордена Ленина институт проблем управления (автоматики и телемеханики) (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ИЗОБРАЖЕНИЯ ТОЧЕЧНЫХ

ИСТОЧНИКОВ

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

Изобретение может быть использовано при решении класса задач большой размерности дискретного программировании (задачи о коммивояжере и при отыскивании ,"наикратчайших деревьев").

Известно устройство для прослеживания и анализа изображения точечных источников.

Оно осушествляет свои функции в два этапа, на первом из которых с помошью волоконно-оптического преобразователя вы- 15 деляются информативные прямоугольники, на втором — выпуклые многоугольники путем сканирования информативных прямоуголь- ников. Устройство использует эвристическое правило, согласно которому замкнутый, Q0 маршрут, составленный объединением панкрат:. чайших замкнутых подмаршрутов на некоторых подмножествах узлов, будет наикратчайшим или близким к нему по длине.

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

Недостатком известного устройства является малое число выделяемых им перспективных ребер, равное tt, или tl. -1, при числе ребер замкнутого маршрута, равного tL . Этот недостаток при использовании метода последовательного улучшения маршрута в дальнейшем вынуждает оперировать с полной матрицей ребер. Второй недостаток заключается в неперспективности "ребер-сторон" выпуклых многоугольников для участия в наикратчайшем дереве, к отыскужанию которого сводятся многие экономические и технические задачи. Третий недостаток состоит в неравномерности сканирования, при котором сканируюшее пятно, исходяшее иэ центров, перекрывает каждый раэ часть пространства, просканированную раньше. Этот недостаток вызывает непроизводительные расходы энергетических и временных ресурсов. К недостаткам устройства следует отнести имеюшие место при выделении некоторых выпуклых.3 многоугольников потери ресурсов на сканирование одних и тех же частей прямоугольников дважды и более раз, хотя эти потери невелики.

Бель изобретения заключается в устра-.,, 0(t ненни этих недостатков.

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

На фиг. 1 показана блок-схема устройства; на фиг, 2 — радиально-кольцева. волоконная матрица, на которую спроектиpeâàêî ноле с расположенными на нем то-) 15 че -и- ыми источниками.

Устройство состоит из блока 1 сдвиг. изображения, полупрозрачного зеркала 2, передающей телевизионной трубки 3, блока!

I выб:ps исследуемого участка изображения,:, .20 вьи.:.1лиепногс в виде радиально-кольцевой волоконной матрицы 4, блока формирования иапряжеш л развертки 5, блоки программы 6, фотоприемников 7 (кольцевого,,: и 8 !,конусного) исследуемого изображеI .1, ния 9.

Блок 1, состоит из оптической системы и управляемого электропривода для поворота зеркала 2 вокруг двух взаимно иернендикулярных осей или иэ оптической .30:

1 системы и дефлектора. Применение той и»!i iiией конструкции блока 1 зависит от иредиявляемь>х к устройству требований в с, бьы ц:спейс г вин U Te 1ности» Волоконно оптин. скан матрица A разбита на четыре,. I35, 1 1 .". ацеитрических ко|и ца КЛ„ ((. = 1, 2, 3, 4) равной ширины и на шестнад- д . . одинаковых конусов (секторов) KJ > (; -1, 2, .-.,: 16). центр матрицы 4-; совпадает с вершинами К и центром 40 дл» всех КЛ;, (Порядковые номер i. u j í= обозначены на чертежах).

КЛ „ большего радиуса имеет бол,щий, 1!46 ио !ei> ь . Пересечение КЛ с К )

6 представ»яет собой усеченный конус

УЕ;, Половина стекловолокон каждоа) ".! и усе ч»еииых кои сов объединена в 001 * " »

iKl ут, иодходящии к -м".е ((. = 1, 2„3, 4) ко;п,цевому фотоприемнику; вто, рая половина < текловолокоп иэ усеченнЫх к :лусон объединена в жгут, подходящий к

j -му (J = 1, 2„..., 16} конусному >,,55! ! фотопоие»»шику. На фиг. 1 показан один кольи=-вой 7 и один конусный 8 фотоприемнй и.

Блок формирования напряжений разверт-!

;ки 5 служит для формирования напряжений к системам горизонтальной и вертикальной раэверток трубки 3.

Два координатных входа блока 6 присо/

:,единены к соответствующим выходам бло ка 5, четыре кольцевых — к выходам соответствующих кочусным фотоприемников

;(на фиг. 1 показаны один кольцевой и один конусный входы), командный — к

;командному выходу блока 5, регистрирую;щий — к выходу трубки 3. Два управляю щих выхода блока 6 присоединены к со .ответствующим входам блока 1, сигнальный и командный — соответственно к сигнальному и командному входам блока 5.

,Регистрирующий выход блока 6 служит для связи данного устройства с внешними уст1

;ройствами или с ЭВМ. Один из двух выходов блока 5 присоединен к системе вертикального (горизонтального) отклонения луча трубки 3.

Устройство для каждого иэ узлов графи

;:разбивает пространство вокруг узла на

) плоские одинаковые конусы, вершины кото,рых совмещены с данным узлом. После

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

Для задачи с сорока восемью узлами осуществлялось разбиение пространства на шесть конусов с выборкой в каждом. конусе ребер двух наименьших длин. Из общего

2 числа =.tL (й -1) = 1128 ребер полумат рицы было отобрано tL = 288 ребер, при чем в их число попади ace сорок восемь ,ребер, образующих наикратчайший цикл. Следует отметить, что методом динамиче- ского программирования, как наиболее точ ным, можно решать задачи с числом узлов tl4 17, т. е. когда имеется в матрице

1г а 289 ребер. Выборка перспективных ребер позволяет значительно повысить раз мерность решаемых задач о коммивояжере методом динамического программирования.

В устройстве пространство разбивается на шестнадцать конусов с выборкой наимеш. щего ребра (ребер) в конусе, приче.". такое разбиение сделано для уменьшения рас:ходов ресурсов на сканирование.

Устройство работает следующим образом, Исследуемое иэображение 9 проектируется через оптический канал блока 1 и полупрозрачное зеркало 2 на фотокатод груб,5 ки 3. На поле расположены узлы (графа)

,в виде точечных источников, световой па-.

;раметр которых резко отличен от парамет-, ! пав пощ . Поле описывается в декартонввой ,системе координат (Х,; ) с началом s ..центре поли. Изображение начинают скани-: ровать по спиральной траектории, исходящей иэ начала координат. В момент встречи сканирующего пятна:с первым по счету узлом на выходе трубки 3 появляется импульс, предписывающий запоминание в па мяти блока 6, координат Х и в виде зна. чений выходных напряжений блока 5, причем в памяти уэпа прйсваивается номер..

На этом этапе работы центр иэображении поля совпадает с центром матрицы 4 и

1 ,центром фотокатода трубки 3. На следуюI шем этапе на вход блока 1 подаютси управ ляюшие воздействия, смещая все изобра .жение параллельно оси Х(У) на величину, равную координате Х(У) первого узла и обратную ей по знаку. Тогда изображение

;первого узла совмешается с центром мат-. рицы 4, после чего устройство производит выборку перспективных ребер, инцидентных первому узлу. Выборка перспективных ребер производится для всех узлов одинаково.

Ниже показан этот процесс для одного нэ узлов, совмещенного на фиг. 2 с цент- ром матрицы 4. Координатами этого узла в системе координат (Х, У) будут (-Ь Х, — Д ). Граница проекции смешенного бло ! ком 1 изображения круглого изображения

;9 на матрицу 4 показана на фиг. 2 толсI

:той линией, ограничивающей расположение узлов, которые на фиг, 1 не показаны, Если на выходах -го кольцевого и -го конусного фотоприемников наблюд ется сигнал, это значит, что внутри усеченного конуса УК„ имеется один или несколько узлов. Блок 6 по наличию сигналов с конусных фотоприемников .. отби; рает среди конусов К „ конусы с узла ми, а среди последних — конус К !

Внутри конуса К „,„„один, несколько или все усеченные конусы УК!! „,!, имеют, узлы. Блок 6 задает сканировать первым 5© конус К,хчу!!,1! с L-пч! е . По сигналу на ! командный вход блока 5 последний запуска

1 ется и начинает вырабатывать напряжени9 .разверток. На этот же вход подаются ко:манды на инвертирование выходных напря жений и соответствуюших переключений внутри блока 5, обеспечиваюших ориенти6 .рованное. сканирование смещенного изобра! женин,псолн 9 н Ма фотокатоде тРУбки 3 фо

1конусам, идентичным К j матрицы 4."

;Траектория сканирования является дискре а«х ",:ной и состоит иэ. дуг концентрических, окружностей, ограниченных данным конусом. Uemp окружностей совпадает с вер,шиной (данным узлом) конуса; направле-! чния движения сканирующего пятна на смеж щ,.,ных дугах противоположны. Каждая сле:, дующая дуга имеет радиус, больший радиу,са предыдушей дуги, но не более, чем на

„:диаметр сканирующего пятна. Переход пят

; на на очередную дугу осуществляется .1и, -,скачком вдоль линии границы конуса. Эта ,,:,траектория изображена на фиг. 2 в одном

: из конусов левой нижней четверти матриць! 4. Там же показано сканирующее пятно с !

:сильно увеличенными диаметром и шагом ." ) . между дугами, причем сканирующее пятно заштриховано. Если блок формирования 5 подает на входы вертикальной отклоняюшей ;системы . трубки 3 синусоиды, то на вход горизонтальной системы — косинусоиду и наоборот. Косинусоида и синусоида могут быть и положительными и отрицательными. .Они образованы от генератора, встроенного .в блок 5 (на чертежах не показан) и имеют

:одно и тоже значение аргумента. Когда при сканиронании К.. ((=Юли., i=maw ) ц 1, пятно проходит через узел, на выходе труб ки 3 появляется импулы., предписывающий

::пропустить в блок 6 координаты (выходные

Зб -напряжения блока 5) этого узла Х=:Х -Д Х ! I и У=У- ЬУ, к которым там сразу прпбавля. ются величины Д Х и Д У ""оответсчаен- но, а результат координаты (Х, У) - запо-, минается в отведенном носителе информации:

4О для узла, расположенного в данный момент

;:в центрах матрицы 4 и фотокатода трубки 3. Туда же помещается длина ребр» между .:указанными узлами, фигурйруюшаися также в е-.

; виде : „Напряжениф; определенного уровня, 45,,которое в этот момент имелось на команд. ном входе блока 6, но в блок не проходиlao. Когда первым сканируется К {б1 ) или когда требуется сканировать несколько несмежных усеченных «снуссн УК!! сннс1 го конуса К е у сканирующее йятно долж. но скачком переместиться на границу УК !

; меньшего радиуса«. Величина скачка задаете

, ся блоком. 6; который подает соответству юший сигнал на сигнальный вход блока 5.

Сканирование прекрашается, как только внутри К (i=mi,ü, )=юг ) отбирается

42735 1 няется правилу, указанному ранее для

K „ „ „. После того, как произойдет выборка реоер по всем информативным К)

«а входы блока 1 поступают соответствующие воздействия, изображение поля смешается так, что очередной по присвоенному номеру узел совмещается с центром л;атрипь., 4 и центром фотокатода трубки

3, и вre действия пс выоорке черспектив пых ребер, инцидентных очередному узлу,. повторяются, После выборки перспективных ребер пс все.„ узлам устройствс преä5,Ф заданное число ребер, иначе после сканирования K (4=tnie,j= i% ) начинает сканироваться К j (J =fActl ) с наименьшим, исключая j,"}ìüô и т„д. Таким образом в конусе K сканирование прекращается после выборки заданного числа ребер, в противоположном случае после того, как будут просканированы все К „()=wig), 1О в которых имеются узлы. После сканирования внутри конуса К. блок 6 предписырт т вает сканирование конуса с минимальным без учета ) =ЮЛИ, т. е. очередность 15 сканирования конусов К направлена в сторону строго повышения номеров i сре- ди конусов К 1, содержащих узлы (v. только такие). Порядок сканирования конусов

К внутри К 1 также согласуется с и повышением j и также сканируется только содержащие узлы К ) . Окончание сканирования любого конуса Kj подчи25 кращает работу так как матрица в блоке

6 перспективных ребер заполнена, и информация о ней будет передана на ЭВМ .или внешние устройства с регистрирующего выхода блока 6. На фиг. 2 при заданном числе перспективных ребер в каждом конусе K>,.равном единице, просканированиые зоны поля заштрихованы и обведены.толстыми линиями. Как видно по фиг. 2 устройство позволяет значительно сократить обследуемую площадь поля.

Предмет изобретения

Устройство для анализа изображения точечных источников, содержащее переда,ющую телевизионную трубку, связанную с блэком формирования напряжений развертки и блоком программы, блок выбора исследуемого участка изображения, оптически связанный с изображением и фотоприемниками, выходы которых соединены с блоком программы, о т л и ч а ю щ е ес я тем, что, с uem.,þ увеличения быстродействия, устройство содержит блок сдвига изсбражения, опти чески связанный с передающей телевизионной трубкой и блоком выбора исследуемого участка изображения, выполненным в виде радиально-кольцевой волоконной матрицы, жгр ть= ат соответствующих зон которой свя-заны с фотоприемниками; причем одни выходы блока программы соединены !: уирав ляюшими входами блока сдвига изображеBBR t другие — со входами блока фор» и ро валил напряжений развертки., 421351

Составитель H (уд и ми

Редактор

)1.Утехина

Гекред 11.Ханеоо

Коррек тор

Предириятие «Г!втент», Москва, l 59. Бережковская наб, 24

Заказ 8806 Изд ж ЦУ „. 7р

ЦНИИИИ Государственного комитета Совета Министров СССР ио делам изобретений и открытий в1осква. 113035, Раушская наб„4