iphone - iPhone/iPad でのフラッドフィルパフォーマンスの問題

Question

私はペイントアプリケーションに取り組んでおり、フラッドフィルアルゴリズムを実装しています。私が実装しているコードは次のとおりです: https://github.com/OgreSwamp/ObjFloodFill/blob/master/src/FloodFill.m

およびviewController.hファイル

 #import <UIKit/UIKit.h>
 #import "AppDelegate.h"

 typedef struct {
 int red;
 int green;
 int blue;
 int alpha;
 } color;


 @interface ViewController : UIViewController
 {
   AppDelegate *appDelegate;
   UIImageView *mainImage;
   UIView *loadingView;
   unsigned char *imageData;
   UIActivityIndicatorView *activityIndicator;
   color selColor;
   color newColor;
   BOOL boolVariable;
   int maxByte;

}
- (IBAction)fn_btnRed:(id)sender;
- (IBAction)fn_btnGreen:(id)sender;
- (IBAction)fn_btnBlue:(id)sender;
- (IBAction)fn_btnSave:(id)sender;
-(void)alertActivityClose;
@end

Viewcontroller.m ファイル

 #import "ViewController.h"
 #import "FloodFill.h"

 @implementation ViewController


 #pragma mark - View lifecycle
 - (void)didReceiveMemoryWarning
 {
   [super didReceiveMemoryWarning];
   // Release any cached data, images, etc that aren't in use.
 }


 - (void)setupImageData
 {
    CGImageRef imageRef = mainImage.image.CGImage;
    if (imageRef == NULL) { return; }
   NSUInteger width = CGImageGetWidth(imageRef);
   NSUInteger height = CGImageGetHeight(imageRef);
   CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
   NSUInteger bytesPerPixel = 4;
   NSUInteger bytesPerRow = bytesPerPixel * width;
   NSUInteger bitsPerComponent = 8;

   maxByte = height * width * 4;
   imageData = malloc(height * width * 4);

   CGContextRef context = CGBitmapContextCreate(imageData, width, height,   bitsPerComponent, bytesPerRow, colorSpace,
                                             kCGImageAlphaPremultipliedLast |     kCGBitmapByteOrder32Big);
  CGColorSpaceRelease(colorSpace);
  CGContextDrawImage(context, CGRectMake(0, 0, width, height), imageRef);
  CGContextRelease(context);
 }

 - (id)initWithNibName:(NSString *)nibNameOrNil bundle:(NSBundle *)nibBundleOrNil
 {
    self = [super initWithNibName:nibNameOrNil bundle:nibBundleOrNil];
    if (self) {
     mainImage = [[UIImageView alloc]initWithImage:[UIImage   imageNamed:@"scaledWhite.png"]];
     [self.view addSubview:mainImage];

      newColor.red = 255;
      newColor.green = 94;
      newColor.blue = 0;
      [self setupImageData];
}
  return self;
}

- (void)updateImage 
{
   CGImageRef imageRef = mainImage.image.CGImage;
   if (imageRef == NULL) { return; }
   NSUInteger width = CGImageGetWidth(imageRef);
   NSUInteger height = CGImageGetHeight(imageRef);
   CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
   NSUInteger bytesPerPixel = 4;
   NSUInteger bytesPerRow = bytesPerPixel * width;
   NSUInteger bitsPerComponent = 8;

   CGContextRef context = CGBitmapContextCreate(imageData, width, height, bitsPerComponent, bytesPerRow, colorSpace, kCGImageAlphaPremultipliedLast ); 

   imageRef = CGBitmapContextCreateImage (context);
   mainImage.image = [UIImage imageWithCGImage:imageRef];  

   CGContextRelease(context);  
   if (boolVariable==YES)
   {
       UIImageWriteToSavedPhotosAlbum(mainImage.image, nil, nil, nil);
   }
   boolVariable=NO;
  }

 - (void)setPixel:(NSUInteger)byte toColor:(color)color 
  {
    imageData[byte] = color.red;
    imageData[byte+1] = color.green;
    imageData[byte+2] = color.blue;
  }

- (BOOL)testByte:(NSInteger)byte againstColor:(color)color 
{
   if (imageData[byte] == color.red && imageData[byte+1] == color.green && imageData[byte+2] == color.blue) {
   return YES;
} 
 else
 {
    return NO;
 }
}

   // This is where the flood fill starts. Its a basic implementation but crashes when  filling large sections.
 - (void)floodFillFrom:(NSInteger)byte bytesPerRow:(NSInteger)bpr {
  int u = byte - bpr;
  int r = byte + 4;
  int d = byte + bpr;
  int l = byte - 4;
  if ([self testByte:u againstColor:selColor]) {
    [self setPixel:u toColor:newColor];
    [self floodFillFrom:u bytesPerRow:bpr];
  }
  if ([self testByte:r againstColor:selColor]) {
    [self setPixel:r toColor:newColor];
    [self floodFillFrom:r bytesPerRow:bpr];
  }
 if ([self testByte:d againstColor:selColor]) {
     [self setPixel:d toColor:newColor];
    [self floodFillFrom:d bytesPerRow:bpr];
 }
 if ([self testByte:l againstColor:selColor]) {
    [self setPixel:l toColor:newColor];
    [self floodFillFrom:l bytesPerRow:bpr];
 }
}
  -(void)shiftingOnMainThread
  {
    [self performSelectorOnMainThread:@selector(updateImage) withObject:nil waitUntilDone:YES];
  }

 - (void)startFillFrom:(NSInteger)byte bytesPerRow:(NSInteger)bpr 
 {
   if (imageData[byte] == 0 && imageData[byte+1] == 0 && imageData[byte+2] == 0) 
   {
     return;
   } 
   else if ([self testByte:byte againstColor:newColor]) 
   {
     NSLog(@"Same Fill Color");
   }
   else 
   {
     // code goes here
     NSLog(@"Color to be replaced");
     [self floodFillFrom:byte bytesPerRow:bpr];
     [self updateImage];
   }
 }
 - (void)selectedColor:(CGPoint)point 
 {
   CGImageRef imageRef = mainImage.image.CGImage;
   if (imageRef == NULL) { return; }
   if (imageData == NULL) { return; }
   NSInteger width = CGImageGetWidth(imageRef);
   NSInteger byteNumber = 4*((width*round(point.y))+round(point.x));
   selColor.red = imageData[byteNumber];
   selColor.green = imageData[byteNumber + 1];
   selColor.blue = imageData[byteNumber + 2];
   NSLog(@"Selected Color, RGB: %i, %i, %i",selColor.red, selColor.green, selColor.blue);
   NSLog(@"Byte:%i",byteNumber);
 }

 - (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event 
{
    UITouch *touch = [touches anyObject];
    CGPoint location = [touch locationInView:mainImage];
    [self selectedColor:location];
    CGImageRef imageRef = mainImage.image.CGImage;
    NSInteger width = CGImageGetWidth(imageRef);
    NSInteger height = CGImageGetHeight(imageRef);

   int x = 0;
   x |= (selColor.red & 0xff) << 24;
   x |= (selColor.green & 0xff) << 16;
   x |= (selColor.blue & 0xff) << 8;
   x |= (selColor.alpha & 0xff);

  int y = 0;
  y |= (newColor.red & 0xff) << 24;
  y |= (newColor.green & 0xff) << 16;
  y |= (newColor.blue & 0xff) << 8;
  y |= (newColor.alpha & 0xff);


  [NSThread detachNewThreadSelector:@selector(shiftingOnMainThread) toTarget:self withObject:nil];
 }
 -(void)alertActivityClose
 {
   [activityIndicator stopAnimating];
   [activityIndicator hidesWhenStopped];
    loadingView.hidden=YES;
 }

- (void)viewDidLoad
{
   [super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
}

 - (void)viewDidUnload
 {
    [super viewDidUnload];
 // Release any retained subviews of the main view.
 // e.g. self.myOutlet = nil;
  }

 - (void)viewWillAppear:(BOOL)animated
 {
   [super viewWillAppear:animated];
 }

 - (void)viewDidAppear:(BOOL)animated
 {
  [super viewDidAppear:animated];
 }

 - (void)viewWillDisappear:(BOOL)animated
 {
[super viewWillDisappear:animated];
 }

 - (void)viewDidDisappear:(BOOL)animated
 {
[super viewDidDisappear:animated];
  }

  - (BOOL)shouldAutorotateToInterfaceOrientation:(UIInterfaceOrientation)interfaceOrientation
  {
   // Return YES for supported orientations
    return (interfaceOrientation != UIInterfaceOrientationPortraitUpsideDown);
  }

   - (IBAction)fn_btnRed:(id)sender 
   {
    newColor.red = 255;
    newColor.green = 0;
    newColor.blue = 0;

   }

  - (IBAction)fn_btnGreen:(id)sender 
  {
    newColor.red = 0;
    newColor.green = 255;
    newColor.blue = 0;

  }

 - (IBAction)fn_btnBlue:(id)sender
 {
    newColor.red = 0;
   newColor.green = 0;
   newColor.blue = 255;

 }

 - (IBAction)fn_btnSave:(id)sender 
 {
   boolVariable=YES;
   [self updateImage];

 }
  @end

ユーザーがアプリケーションを継続的に使用するとパフォーマンスの問題が発生し、小さな部分を埋めるのに約 20 ～ 30 秒かかり、メモリエラーでクラッシュします。

フラッドフィルでこの種の問題が発生した人はいますか?どのように解決しましたか?

score 0 · Accepted Answer

賢明なクラッシュ：塗りつぶしが画像の左端/右端またはピクセルデータの上端または下端にラップするのを妨げるコードは見当たりません。左/右フラッドを制限しないと、予期しない結果が生じる場合があります。トップ/ボトムをオーバーランすると、不正なメモリアクセス (クラッシュ) が発生する可能性が高くなります。

color 構造体は、おそらく 4 つの uint8_t (int ではなく) として定義する必要があります。また、imageData をこの (プロパティサイズの) 構造体へのポインターとして定義し、+0、+1、+2 オフセットをハードコーディングする代わりに、コンパイラーが .red、.green、.blue コンポーネントを処理できるようにします。

(想定される) 値をハードコーディングしているほとんどの場所で、代わりに「sizeof(x)」を使用します。

   NSUInteger bytesPerPixel = sizeof(color);

score 0 · Accepted Answer

パフォーマンスに関しては、インデックスをいじり、ほぼすべてのピクセルアクセスで絶対アドレスの再計算を強制しています (実際のピクセルアクセスは (再帰的な) サブルーチンへの次の呼び出しであるため)。通常、ピクセルアドレスを直接操作する方がはるかに高速です (特に、水平 (左 <-> 右) ランの場合)。

ObjC メソッドのディスパッチによってどれだけのオーバーヘッドが追加されるかはわかりませんが、floodFillFrom:bytesPerRow:、testByte:againstColor:、および setPixel:toColor: を単純な C 関数として書き直すことを検討します。（静的インラインとしてテスト＆設定。）

iphone - iPhone/iPad でのフラッド フィル パフォーマンスの問題

2 に答える 2

Related

Reference

iphone - iPhone/iPad でのフラッドフィルパフォーマンスの問題