Имеется файл довольно большого размера (до 1.8 Гб) в формате RAW (каждый байт которого представляет собой цвет, а адрес этого байта указывает на местоположение точки этого цвета, то есть некодированное изображение с глубиной цвета в 8 бит) – по сути известны координаты x,y и z (цвет)
Необходимо найти все точки черного цвета ($00) и этот массив отсортировать (упорядочить черные пиксели так, чтобы расстояние между ними было наиболее коротким).
Не подскажите наиболее скоростной способ этой реализации?
мой алгоритм работает настолько медленно, что поток на одно чтение файла занимает почти 5 часов!!! ))
Получается что массив нужно постоянно держать в оперативной памяти или использовать FileMapping? Нужно чтобы отсортированное изображение показывалось еще и на канве!
5 февраля 2010 в 12:05
А вы не используйте функции для строк. Они не предназначены для работы с массивами.
Видите ли, функция CreateMapping, равно как и MapViewOfFile, никакого нуля не дописывает. Более того, его там и не должно быть. Это не строка, это массив. Работайте с ним именно функциями для массивов, а не для строк.
Windows вам как раз все читает. Это дальше проблемы идут.
5 февраля 2010 в 0:05
в данном случае файл проецируется в оперу и рассматривается как обычный массив с завершающим символом в конце, не я же нулевым символом придумал обозначать конец строки, завершающий ноль-терминатор – признак конца любой строки в оперативной памяти( его сама функция createmapping дописывает
1.HF:=FileOpen(FileName,fmOpenRead or fmShareDenyWrite); – здесь нормально возвращается размер файла
2.HM:=CreateFileMapping(HF,nil,PAGE_READONLY,0,0,nil);
3.PF:=MapViewOfFile(HM,FILE_MAP_READ,0,0,0); – а здесь уже укороченный получается файл.
4.OutText((PChar(PF))); – вывод содержимого map файла Chart
5.UnmapViewOfFile(PF);
PF – указатель за массив типа Pchar, а длина его содержимого в винде и определяется по нулевому символу в конце. А тут получается, что винданаходит символ $00 (черный пиксел) и думает, что это завершающий символ идальше читать отказывается… (
так тоже пробовал
3.PF:=MapViewOfFile(HM,FILE_MAP_READ,0,0,GetFileSize(HF,nil));
5 февраля 2010 в 0:03
Определите длину файла заранее и ограничьте пределы цикла.
И что это за формат, если вы конец файла обозначаете нулевым символом?
4 февраля 2010 в 19:03
Переделал код с использованием File Mapping'а. По скорости обрабатывает как надо. Но возникла проблема: Признаком конца файла является символ с кодом $00. А у меня такие обозначают черные пиксели. Получается, что как только программа находит этот символ, так обработка файла заканчивается!!
Как обойти не подскажите?
3 февраля 2010 в 21:03
В принципе, в нулевом приближении, действительно, достаточно следовать по траектории. Возможно, стоит разделить файл на более скромные по размеру области и обрабатывать их по отдельности, а затем "склеить" решения?
3 февраля 2010 в 21:02
что же вместо charta использовать? если писать в другой файл, то думаю, что быстрее не будет… хотя памяти лопать будет меньше.
с самим алгоритмом упорядочивания проблемы не вижу – найти точку, затем соседние с ней а дальше рекурсия, но получается, что нужно постоянно держать картинку в памяти. Видимо остается одно FM.
3 февраля 2010 в 21:01
между клетками – нормально. нужно лишь отправить новые координаты для отверстия в формате {x,y,z,t,F}
x – координата по длине рабочего поля
y – координата по ширине поля
z – высота подвеса фокусирующей линзы
t – время в милисекундах, в течение которого происходит плавка материала.
F – 0 or 1 (включить лазер или нет)
Дальше станок уже сам просчитывает на сколько ему двинуть все каретки (на сколько градусов) и двигатели работают все одновременно.
Касаемо программы:
Пробовал я и поблочно обработать – читает то он конечно намного быстрее, а вот как только начинает сравнивать массив с тем же $FF, так опять почти тоже самое (..
3 февраля 2010 в 21:01
Если вы на каждый байт, то есть каждый пиксель, продолжите менять текст в полоске статуса, то так и будет. Да, и Chart1, боюсь, тоже изрядно тормозит добавление точек – не говоря уже о том, сколько ему памяти на них нужно. Попробуйте для начала хотя бы обрабатывать точки порциями, например, по 1024.
Что же до упорядочения, то здесь однозначно лучшего алгоритма нет, и надо разбираться в деталях. Как вы упорядочивать-то собрались?
3 февраля 2010 в 20:05
Насчет того, что скорость не сильно увеличится, если читать блоками – это ты сильно ошибаешься
3 февраля 2010 в 20:05
Есть вопрос – а если лазер проходит между клетками по диагонали, это нормально?
т.е. в ситуации
FF 00
00 FF
перейти из клетки 00 в 00
3 февраля 2010 в 20:00
Постараюсь описать более подробно.
Пример RAW файла:
FF FF 00 FF FF FF 00 FF 00 FF FF 00 FF 00 FF FF 00 FF 00 FF FF FF 00 FF FF
т.е. изображение с разрешением 5х5 пиксела будет такое:
FF FF 00 FF FF
FF 00 FF 00 FF
FF 00 FF 00 FF
FF 00 FF 00 FF
FF FF 00 FF FF
где FF – пиксели белого цвета, 00 – пиксели черного цвета,
т.е на рисунке будет буква О
я делаю программу для лазерного станка, но если массив отправить на станок как есть неотсортированно (т.е. так, как его печатает например принтер – последовательно пропечатывает сначала линию строки, а потом двигает лист бумаги еще на один шаг и печатает следующую строку и т.д.) то необходимо частое включение питания лазерной головки там, где нужно сделать отверстие, а там где его не нужно делать питания лазера приходится отключать и если так дело дальше пойдет, то жизни газового лазера моего станка скоро придет конец! да и долго это довольно!
Нужно отсортировать массив изображения таким образом, чтобы головка лазерного станка плавно без выключения питания вырезала как в примере букву О. Т.е. найти все соседние точки, которые нужно также прожечь. А после того, как элемент готов, выключить лазерную головку и перейти на следующий элемент (например следующую букву).
здесь у меня код потока, для обработки файла изображения. После чего данные заносятся массив в компонент TChart (который заодно показывает все изображение так как оно будет выполнено).
То, что не относится к проблеме здесь сокращено…
procedure GeneratingCode.Execute;
var
f: TextFile;
buf: string[1];
StatusBarComp:Tcomponent;
x,y,n:integer;
i,l:Integer;
begin
i:=0;
stop:=false;{флаг запуска потока}
searchfinished:=false;{флаг уведомления потоком главной формы}
myComponent:=MainForm.MDIChildren[0].FindComponent('JvDBRichEdit1');
AssignFile(f, MainForm.MDIChildren[0].Caption);
Reset(f);
StatusBarComp:=MainForm.MDIChildren[0].FindComponent('StatusBar1');
while not EOF(f) do
begin
if stop=false then
begin
read(f, buf);
inc(i);{инкремент адреса, где располагается пиксель}
IF (ord(buf[1])<>$FF) then
begin
y:=i div 10000;{координата. 10000 – высота изображения в пикселях}
x:=i mod 20000;{координата. 20000 – ширина изображения в пикселях}
GridForm.Chart1.Series[0].AddXY(x, y, '', clblack);{вывод изображения}
end;
TStatusBar(StatusBarComp).SimpleText:='Processed '+IntToStr(i);
end else
begin
TStatusBar(StatusBarComp).SimpleText:='Interrupted';
break;
end;
end;
CloseFile(f);
searchfinished:=true;
end;
Читается все конечно побайтно, но если читать блоком а потом обрабатывать, скорость думаю не сильно увеличится, сейчас она примерно 1 кБ/c )))
3 февраля 2010 в 1:00
Я бы попробовал файл mapping-ом в память, но это без учета деталей задания. Неизвестно еще, что именно требуется-то. Хотя бы сколько раз по нему проходить придется.
2 февраля 2010 в 21:02
А обращаться к файлу и считывать оттуда по частям, по мере обработки? да, просьба уточнить задание
2 февраля 2010 в 21:01
Если задача критична по быстродействию, то я думаю, что это хороший выход, да и 1,8 Гб это не так уж и много
2 февраля 2010 в 21:00
держать 1,8 Гб в оперативке изврат, имхо.
это, случаем, не конкурсное задание?
2 февраля 2010 в 20:05
Ну в наше время 1,8 Гб можно и в оперативной памяти держать,
и да, не очень понятно задание.
2 февраля 2010 в 18:01
> Необходимо найти все точки черного цвета ($00) и этот массив отсортировать (упорядочить черные пиксели так, чтобы расстояние между ними было наиболее коротким).
Не вполне понятно, кого именно вы собираетесь сортировать? Какое "расстояние между пикселями" требуется минимизировать? И какого порядка количество черных пикселей?
2 февраля 2010 в 17:00
выложите свою версию реализации пожалуйста, хочется посмотреть, в каких местах ваш алгоритм слаб.